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
| class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1)
return head;
ListNode currHead = head, nextHead = head;
ListNode prevTail = new ListNode(0), dummy = prevTail;
while (currHead != null) {
int count = 0;
while (count < k && nextHead != null) {
nextHead = nextHead.next;
count += 1;
}
if (nextHead == null && count < k) {
prevTail.next = currHead;
break;
}
ListNode newHead = reverse(currHead, k);
prevTail.next = newHead;
prevTail = currHead;
currHead = nextHead;
}
return dummy.next;
}
private ListNode reverse(ListNode head, int k) {
ListNode prev = null, curr = head;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
|
需要记录上一个group的end, 这个group的start以及下一个group的start.
我没想到的是如果走k次的过程中, 我们遇到了null, 这是分情况的. 一种是刚好走了k次到了null, 此时最后的group是刚好有k个node, 此时需要reverse; 另一种情况就是最后一个group不够k个node, 因此不需要reverse. 这也是23行干的事情.
还有就是reverse的时候, 我一开始直接傻乎乎的把整个list给reverse了, 但实际上应该只reverse当前group里的node. 同时我reverse后返回的东西还以为是返回curr, 其实在最后一次循环前curr已经更新到了下一个group的start. 因此我们还是应该返回prev.
时间复杂度: O(n)
空间复杂度: O(1)
