25. Reverse Nodes in k-Group Leetcode Java

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:

This problem is a general problem of 24. Swap Nodes in Pairs Leetcode . Instead of swapping two nodes a time, now we need to swap k nodes each time. The idea is find the pre and end node of the k-group nodes, and do the reverse for those nodes. The reverse is simple, insert each processing node in between the pre node and the pre.next node. Here I use a runner node to find the kth node from the pre. 

 public ListNode reverseKGroup(ListNode head, int k) {  
    if(head==null || k<=1) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode pre=predummy;  
    ListNode cur=head;  
    while(pre!=null && pre.next!=null){  
      ListNode runner=pre;  
      for(int i=0;i<k && runner!=null;i++) runner=runner.next;  
      if(runner==null) return predummy.next;  
      ListNode newPre=cur;  
      ListNode end=runner.next;  
      while(cur!=end){  
        ListNode temp=cur.next;  
        cur.next=pre.next;  
        pre.next=cur;  
        cur=temp;  
      }  
      newPre.next=cur;  
      pre=newPre;  
    }  
    return predummy.next;  
   }  

Another simple solution is to maintain a stack with size k. Push the node to the stack till its size reaches k, then pop all the elements out from the stack, which is also the process of reversing the k-group nodes. 

 public ListNode reverseKGroup(ListNode head, int k) {  
     if (k<2) return head;  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=head;  
     ListNode pre=preDummy;  
     Stack<ListNode> sl=new Stack<ListNode>();  
     int i=1;  
     while (head!=null){  
       if(i%k!=0){  
         sl.push(head);  
         head=head.next;  
         i++;  
       }  
       else {  
         pre.next=head;  
         pre=pre.next;  
         head=head.next;  
         while (!sl.isEmpty()){  
           ListNode temp=sl.pop();  
           pre.next=temp;  
           pre=pre.next;  
         }  
         pre.next=head;  
         i++;  
       }  
     }  
     return preDummy.next;  
   }