My Weblog

Blog about programming and math

Reversing the linked list at some given position

Today I got a question to reverse a linked at every kth position. Lets say if we have a linked list
1->2->3->4->5->6->7->8->9->10 and k is 3 then output should be 3->2->1->6->5->4->9->8->7->10. After writing codes in Haskell, getting into pointer stuff mindset is always hard for me. This can be written in 3 lines using Haskell .

import Data.List

breakList :: ( Show a ) => [ a ] -> Int -> [ a ]
breakList [] _ = []
breakList xs k = reverse p ++ breakList q k  where
       ( p , q ) = splitAt k xs   

*Main> breakList [ 1 , 2, 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] 3
[3,2,1,6,5,4,9,8,7,10]                         

Now lets try this one using pointers. In reverse function, we are passing the starting address of every kth element. After reversing the segment, we are calling the reverse function recursively on every segment and copying the starting address of each segment ( prev ) in head->next which is technically after reversing the segment became the end of segment.

#include<cstdio>
#include<iostream>
using namespace std;

struct node
 {
        int data;
        struct node *next ;
 };

struct node *reverse(struct node *head, int k)
{
    struct node* curr = head;
    struct node* prev = NULL;
    int count = 0;
    //reverse the k nodes of this segment. During the process, prev will point to first node and
    // head->next will null  
    while (curr != NULL && count < k )
    {
       struct node *t  = curr->next;
       curr->next = prev;
       prev = curr;
       curr = t ;
       count++;
    }
    
    //copy the address returned by reverse to head->next. 
    if( curr  !=  NULL)
        head->next  = reverse( curr   , k);

    return prev;
}

Testing code. print and push_back functions are taken from my previous implementation.


void print(struct node *curr)
        {
                while(curr!=NULL) printf("%d -> ",curr->data),curr=curr->next;
                printf("\n");
        }

void push_back(struct node **ref,int n)
        {
                struct node *tmp=(struct node*) malloc (sizeof (struct node ));
                tmp->data=n;
                tmp->next=NULL;
                if(*ref==NULL) *ref=tmp;
                else
                {
                        struct node *curr=*ref;
                        while(curr->next!=NULL) curr=curr->next;
                        curr->next=tmp;
                }

        }



int main()
{
        struct node *q = NULL;
        for(int i=1;i<=20;i++)push_back(&q,i);printf("the q list is \n");print(q);
        struct node *p = reverse ( q , 4 );
        print ( p ) ;
}

Mukeshs-MacBook-Pro:Agda mukeshtiwari$ ./a.out 
the q list is 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 
4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 12 -> 11 -> 10 -> 9 -> 16 -> 15 -> 14 -> 13 -> 20 -> 19 -> 18 -> 17 -> 

If you have any suggestions then please let me know.

Advertisements

January 9, 2013 - Posted by | Haskell, Programming | ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: