Reverse every k nodes of a linked list

Question

I am preparing for a technical interview and I am stuck at writing this program to reverse every k nodes of a linked list.

For example

1->2->3->4->5->6 //Linked List
2->1->4->3->6->5 //Output for k=2

EDIT:

Here is my code. I get only 6->5 as output.

struct node* recrev(struct node* noode,int c)
{
 struct node* root=noode,*temp,*final,*prev=NULL;
 int count=0;
 while(root!=NULL && count<c)
 {
  count++;
  temp=root->link;
  root->link=prev;
  prev=root;
  root=temp;
 }
 if(temp!=NULL)
   noode->link=recrev(temp,c);
 else
   return prev;

}

Any help is appreciated. Thanks.

EDIT: I tried to implement Eran Zimmerman's Algorithm as below.

struct node* rev(struct node* root,int c)
{
 struct node* first=root,*prev,*remaining=NULL;
 int count=0;
 while(first!=NULL && count<c)
 {

    count++;
    prev=first->link;
    first->link=remaining;
    remaining=first;
    first=prev;
 }
 return remaining;
}
struct node* recc(struct node* root,int c)
{
 struct node* final,*temp,*n=root,*t;
 int count=0;
 while(n!=NULL)
 {
       count=0;
       temp=rev(n,c);
       final=temp;


    while(n!=NULL && count<c)
    {   
     printf("inside while: %c\n",n->data);  // This gets printed only once
     if(n->link==NULL) printf("NULL");    //During first iteration itself NULL gets printed
        n=n->link;
        final=final->link;
        count++;
    }

 }
 final->link=NULL;
 return final;
}

http://stackoverflow.com/questions/1801549/reverse-a-singly-linked-list — celavek, Aug 21 '11 at 12:19
+1: After looking at your code, I believe you think carefully to work your own answer out, although it's may not be the optimal one. — Eric Z, Aug 21 '11 at 13:09
I think this is a duplicate of : http://stackoverflow.com/questions/6982593/reversing-a-singly-linked-list-when-a-block-size-is-given — vine'th, Aug 21 '11 at 14:38

score 5 · Answer 1 · edited Feb 01 '15 at 21:31

Yeah, I have never been a fan of recursion, so here is my shot at it using iteration:

  public Node reverse(Node head, int k) {
       Node st = head;
       if(head == null) {
         return null;
       }

       Node newHead = reverseList(st, k);
       st = st.next;  

       while(st != null) {
         reverseList(st, k);
         st = st.next;
       } 

       return newHead

  }


 private Node reverseList(Node head, int k) {

      Node prev = null;
      Node curr = head;
      Node next = head.next;

      while(next != null && k != 1){
       curr.next = prev;
       prev = curr;
       curr = next;
       next = next.next;
       --k;
      }
      curr.next = prev;

      // head is the new tail now.
      head.next = next;

      // tail is the new head now.
      return curr;
 }

score 2 · Answer 2 · answered Aug 21 '11 at 16:54

Here is a pseudo code.

temp = main_head = node.alloc ();
while ( !linked_list.is_empty () )
{
    push k nodes on stack
    head = stack.pop ();
    temp->next = head;
    temp = head;
    while ( !stack.empty () )
    {
        temp->next = stack.pop ();
        temp = temp->next;
    }
}

I have made a demo implementation of this code. Pardon for the messy implementation. This will work for any value of k. Each k sized segment is reversed separately in the inner loop and the different segments are linked with each other in the outer loop before entering the inner one. temp traces the last node of the k sized sublist and head holds the next value of the next sublist, and we link them. An explicit stack is used to do the reversal.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
  int a;
  struct _node *next;
} node_t;

typedef struct _stack {
  node_t *arr[128];
  int top;
} stack_t;

void stk_init (stack_t *stk)
{
  stk->top = -1;
}

void push (stack_t *stk, node_t *val)
{
  stk->arr[++(stk->top)] = val;
}

node_t *pop (stack_t *stk)
{
  if (stk->top == -1)
   return NULL;
  return stk->arr[(stk->top)--];
}

int empty (stack_t *stk)
{
  return (stk->top == -1);
}

int main (void)
{
  stack_t *stk = malloc (sizeof (stack_t));
  node_t *head, *main_head, *temp1, *temp;
  int i, k, n;

  printf ("\nEnter number of list elements: ");
  scanf ("%d", &n);
  printf ("\nEnter value of k: ");
  scanf ("%d", &k);

  /* Using dummy head 'main_head' */
  main_head = malloc (sizeof (node_t));
  main_head->next  = NULL;
  /* Populate list */
  for (i=n; i>0; i--)
  {
    temp = malloc (sizeof (node_t));
    temp->a = i;
    temp->next = main_head->next;
    main_head->next = temp;
  }

  /* Show initial list */
  printf ("\n");
  for (temp = main_head->next; temp != NULL; temp = temp->next)
  {
    printf ("%d->", temp->a);
  }

  stk_init (stk);

  /* temp1 is used for traversing the list
   * temp is used for tracing the revrsed list
   * head is used for tracing the sublist of size 'k' local head
   * this head value is used to link with the previous
   * sublist's tail value, which we get from temp pointer
   */
  temp1 = main_head->next;
  temp = main_head;
  /* reverse process */
  while (temp1)
  {
    for (i=0; (temp1 != NULL) && (i<k); i++)
    {
      push (stk, temp1);
      temp1 = temp1->next;
    }
    head = pop (stk);
    temp->next = head;
    temp = head;
    while (!empty (stk))
    {
      temp->next = pop (stk);
      if (temp->next == NULL)
        break;
      temp = temp->next;
    }
  }
  /* Terminate list with NULL . This is necessary as
   * for even no of nodes the last temp->next points
   * to its previous node after above process
   */
  temp->next = NULL;

  printf ("\n");
  for (temp = main_head->next; temp != NULL; temp = temp->next)
  {
    printf ("%d->", temp->a);
  }

  /* free linked list here */

  return 0;
}

Eran Zimmerman Gonen · Answer 3 · 2011-08-21T13:33:19.757

1

I would do something like this:

init curr (node pointer) to point to the beginning of the list.
while end of list is not reached (by curr):
- reverse(curr, k)
- advance curr k times

and reverse is a function that reverses the first k elements starting from curr.

this might not be the most elegant or the most efficient implementation, but it works and is quite simple.

~~to answer regarding the code you added:~~

you returned prev, which is constantly being advanced. you should return the beginning of the list.

edited Aug 21 '11 at 13:33

answered Aug 21 '11 at 12:18

Eran Zimmerman Gonen

4,375
1
19
31

I tried to implement your algorithm, but with no success. Once I reverse the list upto k nodes, my original list gets lost and am not able to continue the loop. If you could implement it, pls share the code.. – Vivek Aug 21 '11 at 15:01
please post the code you tried, it might be quicker to identify a single problem than to rewrite the code from scratch. – Eran Zimmerman Gonen Aug 21 '11 at 15:14

Eric Z · Accepted Answer · 2011-08-21T13:12:15.403

1

I like you recursion, although it may be not the best solution. I can see from your code that you think it deep when you design it. You're just one step away from the answer.

Cause: You forget to return the new root node in your recursion case.

if(temp!=NULL)
   noode->link=recrev(temp,c);
   // You need return the new root node here
   // which in this case is prev:
   // return prev;
 else
   return prev;

edited Aug 21 '11 at 13:12

answered Aug 21 '11 at 13:02

Eric Z

14,327
7
45
69

I don't get you. Could you paste the modified code here so that I can understand better. – Vivek Aug 21 '11 at 14:05

Arvind · Answer 5 · 2012-06-14T12:13:49.320

The following solution uses extra space for storing pointers,and reverses each chunk of list separately. Finally,the new list is built. When I tested, this seemed to cover the boundary conditions.

template <typename T>
struct Node {
T data;  
struct Node<T>* next;
Node()  {  next=NULL; } 
};
template <class T>
void advancePointerToNextChunk(struct Node<T> * & ptr,int  & k)  {
int count =0;  
while(ptr && count <k )  {
    ptr=ptr->next; 
    count ++; 
}
k=count;}

/*K-Reverse Linked List */
template <class T>  
 void kReverseList( struct Node<T> * & head,  int k){ 
 int storeK=k,numchunk=0,hcount=0;
 queue < struct Node<T> *> headPointerQueue;  
 queue <struct Node<T> *>  tailPointerQueue; 

 struct Node<T> * tptr,*hptr;
 struct Node<T> * ptr=head,*curHead=head,*kReversedHead,*kReversedTail;
 while (ptr) {
 advancePointerToNextChunk(ptr,storeK);
 reverseN(curHead,storeK,kReversedHead,kReversedTail);
 numchunk++; 
 storeK=k; 
 curHead=ptr;
 tailPointerQueue.push(kReversedTail),headPointerQueue.push(kReversedHead); 
 }
 while( !headPointerQueue.empty() ||  !tailPointerQueue.empty() )  {
    if(!headPointerQueue.empty()) {
        hcount++;  
        if(hcount == 1) { 
            head=headPointerQueue.front(); 
            headPointerQueue.pop();
        }
        if(!headPointerQueue.empty()) {
        hptr=headPointerQueue.front(); 
        headPointerQueue.pop(); 
        }
    }
    if( !tailPointerQueue.empty() ) {
        tptr=tailPointerQueue.front();  
        tailPointerQueue.pop(); 
    }
    tptr->next=hptr;  
 }
 tptr->next=NULL;}

 template <class T> void reverseN(struct Node<T> * & head, int k, struct Node<T> * &   kReversedHead, structNode<T> * & kReversedTail ) {
  struct Node<T> * ptr=head,*tmp;  
  int count=0;
  struct Node<T> *curr=head,*nextNode,*result=NULL; 
  while(curr && count <k) {
      count++; 
      cout <<"Curr data="<<curr->data<<"\t"<<"count="<<count<<"\n"; 
      nextNode=curr->next;  
      curr->next=kReversedHead; 
      kReversedHead=curr;
      if(count ==1 )  kReversedTail=kReversedHead; 
      curr=nextNode;
  }}

score 0 · Answer 6 · answered Aug 21 '13 at 06:20

public class ReverseEveryKNodes<K>
{
      private static class Node<K>
      {
        private K k;
        private Node<K> next;

        private Node(K k)
        {
            this.k = k;
        }
      }
private Node<K> head;
private Node<K> tail;
private int size;

public void insert(K kk)
{
    if(head==null)
    {
        head = new Node<K>(kk);
        tail = head;
    }
    else
    {
        tail.next = new Node<K>(kk);
        tail = tail.next;
    }
    size++;
}

public void print()
{
    Node<K> temp = head;
    while(temp!=null)
    {
        System.out.print(temp.k+"--->");
        temp = temp.next;
    }
    System.out.println("");
}

public void reverse(int k)
{
    head = reverseK(head, k);
}

Node<K> reverseK(Node<K> n, int k)
{
    if(n==null)return null;

    Node<K> next=n, c=n, previous=null;
    int count = 0;
    while(c!=null && count<k)
    {
        next=c.next;
        c.next=previous;
        previous=c;
        c=next;
        count++;
    }
    n.next=reverseK(c, k);
    return previous;
}

public static void main(String[] args)
{
    ReverseEveryKNodes<Integer> r = new ReverseEveryKNodes<Integer>();
    r.insert(10);
    r.insert(12);
    r.insert(13);
    r.insert(14);
    r.insert(15);
    r.insert(16);
    r.insert(17);
    r.insert(18);
    r.print();
    r.reverse(3);
    r.print();
}
}

score 0 · Answer 7 · answered Aug 21 '11 at 13:21

(I'm assuming this is a singly linked list.) You can keep a temporary pointer (lets call it nodek) and advance it k times in a while loop. This will take O(k). Now you have a pointer to the start of the list and to the last element of the sublist. To reverse here, you remove from head which is O(1) and add to nodek which is O(1). Do this for all elements, so this is O(k) again. Now update root to nodek, and run the while loop on nodek again (to get the new position of nodek) and repeat this whole process again. Remember to do any error checking along the way. This solution will run at O(n) with only O(1) extra space.

Reverse every k nodes of a linked list

7 Answers7

Linked

Related