-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0025.java
More file actions
79 lines (73 loc) · 2.75 KB
/
Copy pathSolution0025.java
File metadata and controls
79 lines (73 loc) · 2.75 KB
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 25. K 个一组翻转链表
/**
* 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; }
* }
*/
/*
“92.反转链表II”是只反转一次，逻辑相似
1、指针含义
1）root：哨兵节点
2）pre：上一组链表的尾节点
3）start：当前组链表的头节点
4）end：当前组链表的尾节点
5）next：下一组链表的头节点
2、当有下一组时，遍历k次找到新的当前组的尾节点end，如果不足k个节点则结束
3、标记下一组的头节点next，用于后续与上一组连接
4、标记当前组的头节点start，尾节点下一指针指向空，使得当前组链表独立
5、当前组链表反转，返回新的头节点，上一组链表的尾节点pre连接当前组新的头节点end，新的尾节点start连接下一组的头节点next
6、重新初始化指针指向，pre、end指向start，准备下一轮处理
0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
root/pre/end
=============================================================
0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
root/pre end
=============================================================
0 → 1 → 2 → 3 4 → 5 → 6 → 7 → 8
root/pre start end next
=============================================================
0 → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8
root/pre end start next
=============================================================
0 → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8
root pre/end/start next
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode root = new ListNode(0, head);
ListNode pre = root;
ListNode end = root;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode next = end.next;
ListNode start = pre.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = start;
}
return root.next;
}
// 206.反转链表
private ListNode reverse(ListNode head) {
ListNode before = null, after;
while (head != null) {
after = head.next;
head.next = before;
before = head;
head = after;
}
return before;
}
}