Tuesday, February 2, 2016

Reverse a Linked List in groups of given size

Question:

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3
Output:  3->2->1->6->5->4->8->7->NULL.

Inputs:   1->2->3->4->5->6->7->80->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL.

Solution:

      /**
        * Reverse every k nodes in a given linked list
        *
        * @param l
        * @param k
        * @return
        */
       public ListNode ReverseBlock(ListNode l, int k)
       {
              if(l==null) {
                     return null;
              }
              else {
                     int count=0;
                     ListNode current, prev, next;
                     current=l;
                     prev=next=null;
                     while(current!=null && count<k){
                           next = current.next;
                           current.next = prev;
                           prev=current;
                           current=next;
                           count++;
                     }
                     // reverse remaining block of nodes
                     if(next!=null) {
                           l.next = ReverseBlock(next, k);
                     }
                     // return new header node
                     return prev;
              }

       }

No comments:

Post a Comment