GuilinDev
Lc0025
05 August 2008
25 - 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.
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.
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’
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list’s nodes, only nodes itself may be changed.
题意和分析
这道题要求以k个结点为一组进行翻转，实际上是把原链表分成若干小段，然后分别对其进行翻转，以题目中给的例子来看，对于给定链表1->2->3->4->5，一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node，那么我们加入dummy node后的链表变为-1->1->2->3->4->5，如果k为3的话，我们的目标是将1,2,3翻转一下，那么我们需要一些指针，pre和next分别指向要翻转的链表的前后的位置，然后翻转后pre的位置更新到如下新的位置：
1
2
3
4
5
6
7
-1->1->2->3->4->5
| |
pre next
-1->3->2->1->4->5
| |
pre next
以此类推，只要next走过k个节点，就可以进行局部翻转了。
也可以使用递归来做，我们用head记录每段的开始位置，current记录结束位置的下一个节点，然后我们调用reverse函数来将这段翻转，然后得到一个newHead，原来的head就变成了末尾，这时候后面接上递归调用下一段得到的新节点，返回newHead即可。
代码
Iterative的办法
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {//1->2->3->4->5 : Say k is 3
if(k==1) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode ptr1 = dummy;//boundary before the 1st node
ListNode ptr2 = dummy;//boundary after the kth node
int count = 0;
boolean delete = false;//For deleting the last dummy node
while(count<k){//loop till the kth element : Till 3 in this case
count++;
ptr2=ptr2.next;
if(ptr2==null) break;//if before reaching kth element ptr2 is null, break out of the loop. Example 1->2
if(count==k){
if(ptr2.next==null){
ptr2.next = new ListNode(-1);//dummy2
delete = true;
}
ptr2 = ptr2.next;
count = 0;//Make count 0 to again start with the next group
ptr1 = reverseK(ptr1,ptr2);
ptr2 = ptr1;
}
}
if(delete) ptr1.next = null;
return dummy.next;
}
private ListNode reverseK(ListNode ptr1, ListNode ptr2){//ptr1->|1->2->3|->4->5 : ptr1 is dummy and ptr2 is 4 here
ListNode prev = ptr1;
ListNode temp1 = ptr1.next;
ListNode temp2 = ptr1.next.next;
while(temp1!=ptr2){
temp1.next = prev;//In the first iteration 1 points to ptr1, Last iteration 3->2
prev = temp1;//last iteration prev becomes 3
temp1 = temp2;
temp2 = temp2.next;
}
ptr1.next = prev;//Now a reversed circular list is created, because 3<-ptr1<-1<-2<-3
while(prev.next!=ptr1){
prev=prev.next;//till prev points to 1
}
//1 must point to 4
prev.next = ptr2;//K List now is reversed: ptr1->3->2->1->4->5
return prev;
}
}
迭代的办法比较繁琐，知道递归的办法即可，时间和空间都是O(n)
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
29
30
31
32
33
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
count--;
}
head = curr;
}
return head;
}
}