25. Reverse Nodes in k-Group
Description
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked 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
Answer
Solution 1
The first method is using recursion, that intially deal with the last part of link and it is easy to understand.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public ListNode reverseKGroup(ListNode head, int k) { int count=0; ListNode cur = head; while(cur!=null&&count!=k){ // Counting Number and stop if the last several nodes number less than k. cur = cur.next; count++; } if(count==k){ // Deal with last parts at first. cur = reverseKGroup(cur,k); while(count>0){ // reverse links ListNode next = head.next; head.next = cur; // link now head(future tail) to next group head. cur = head; head = next; count--; } head = cur; } return head; } } |
assume a link with 5 nodes and K=3.
Solution 2
The second solution contrary to the former, deal with the links from head to tail.
In every group we need to locate tail and previous node of head.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public ListNode reverseKGroup(ListNode head, int k) { if(head==null||k<2) return head; ListNode res = new ListNode(0); res.next = head; ListNode pre = res, tail = res; int count=0; while(true){ count= k; while(tail!=null&&count>0){ tail = tail.next; count--; } if(tail==null) break; head = pre.next; while(pre.next!=tail){ ListNode temp = pre.next; pre.next = temp.next;// enable pre node to connect real tail step by step. temp.next = tail.next; tail.next = temp; } pre = head; tail = head; } return res.next; } |
assume a link with 5 nodes and K=3.
