方針
リストをグループごとに処理します。各グループの先頭から k - 1 個のリンクをたどり、k 番目のノードを探します。残りのノードが k 個未満なら、その末尾部分は元の順序を保つ必要があるため処理を終了します。グループを作れる場合は、グループの次のノードを groupNext に保存し、グループ内のリンクを groupNext に向けて反転します。反転の開始時に前ノードを groupNext にしておくと、反転後、元のグループ先頭が変更されていない末尾部分を指します。
k 番目のノードが新しいグループの先頭になり、元の先頭ノードが新しい末尾になります。前のグループの末尾を新しい先頭に接続します。最初のグループの場合はリスト全体の先頭を更新します。その後、末尾になった元の先頭ノードから次のグループを処理します。新しいリストノードは作成せず、入力の全ノードを再利用します。
ノード数を N とすると、各ノードを定数回訪問するため、時間計算量は O(N) です。補助空間計算量は O(1) です。
Java
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode groupPrevious = null;
ListNode groupStart = head;
while (groupStart != null) {
ListNode kth = groupStart;
for (int i = 1; i < k && kth != null; i++) {
kth = kth.next;
}
if (kth == null) {
break;
}
ListNode groupNext = kth.next;
ListNode previous = groupNext;
ListNode current = groupStart;
while (current != groupNext) {
ListNode next = current.next;
current.next = previous;
previous = current;
current = next;
}
if (groupPrevious == null) {
head = kth;
} else {
groupPrevious.next = kth;
}
groupPrevious = groupStart;
groupStart = groupNext;
}
return head;
}
}