Reverse Nodes in k-Group

Reverse Nodes in k-Group

 

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 

 

Naive Way: 如何reverse Linked List。是护住最后一个节点，不断的往后insert节点，那么reverse k 个也是一样的。护住的可以是起点也可以是终点，但这道题要求最后不够k 个保持原样，护住起点不能够有效将最后多出部分写入大循环，护住终点的方法则可以先判断是否找到终点来对付这种情况。

 

算法复杂度O(n), space O(1)。第一次将节点插入终点后面的时候，我记下了新的起点的位置，这样就不用再完成k个再遍历至那里。

  /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode reverseKGroup(ListNode head, int k) {  
     ListNode fakeHead = new ListNode(0);  
     ListNode cur = fakeHead, tail = cur;  
     fakeHead.next = head;  
     int i = 0;  
     while(tail!=null){  
       for(i = 0;i < k && tail.next!=null;i++)  
         tail = tail.next;  
       if(i<k) return fakeHead.next;  
       ListNode nextCur = null;  
       while(cur.next!=tail){  
         ListNode temp = cur.next;  
         if(nextCur==null) nextCur = temp;  
         cur.next = temp.next;  
         temp.next = tail.next;  
         tail.next = temp;  
       }  
       cur = nextCur;  
       tail = cur;  
     }  
     return fakeHead.next;  
   }  
 }  

 

 

 

Improved Way: 在Discuss里还有一种recursive的方法，就是将翻转k个写进一个子函数，每次调用后把它接起来，觉得O(1) space 还是不适合recursive。