绝世好题。
主函数中的dummy对于begin来说就好比是helper函数reverse中的first对于cur一样, 后面的两个节点遍历的过程中都要逐渐往后，所以返回最开始的节点的都需要之前用一个节点纪录
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
| /**
* 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 begin;
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
begin = dummy;
int i = 0;
while (head != null) {
++i;
if (i % k == 0) {
begin = reverse(begin, head.next); // 0 1(b) 2 3(h) 4 5
head = begin.next; // 3(h) 2 1(b) 4; head = begin.next
} else {
head = head.next;
}
}
return dummy.next;
}
// exclusive: prev: needed; end: as null
// partial; smooth begin, modified part, end
public ListNode reverse(ListNode begin, ListNode end) {
ListNode cur = begin.next;
ListNode first = cur;
ListNode prev = begin;
ListNode next;
while (cur != end) { // end: outside this part
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
begin.next = prev;
first.next = cur;
return first;
}
}
|