Invert all k nodes of a linked list

Question

I'm getting ready for a technical interview, and I'm stuck writing this program to cancel all k nodes of a linked list.

for instance

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 Zimmermann's algorithm as shown 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; } 

Answer 1

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

Reason . You forget to return the new root node to recursion.

 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; 

Answer 2

Yes, 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; } 

Answer 3

Here is the 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 made a demo implementation of this code. Sorry for the messy implementation. This will work for any value of k . Each segment of size k completely changes separately in the inner loop, and different segments are connected to each other in the outer loop before introducing the inner one. temp keeps track of the last node of a k-size sublist, and head contains the next value of the next sublist, and we bind them. An explicit stack is used to perform a U-turn.

 #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 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; } 

Answer 4

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 changes the first k elements, starting with curr.

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

to respond to the added code:

you have returned prev, which is constantly advancing. You must return the beginning of the list.

Answer 5

(I assume this is a linked list). You can save the temporary pointer (let's call it nodek ) and translate it k times into the while loop. It takes O (k). Now you have a pointer to the beginning of the list and to the last element of subscriptions. To undo here, you remove from the 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 upgrade root to nodek and run the while loop on nodek again (to get the new nodek position) and repeat the whole process again. Remember to do error checking along the way. This solution will work in O (n) only with the extra space O (1).

Answer 6

The following solution uses additional storage space for pointers and expands each block of the list separately. Finally, a new list is built. When I tested, it 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; }} 

Answer 7

 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(); } }