链表专题Ⅱ—反转基础
206. 反转链表
内容概览
| 题目 |
说明 |
| 带虚拟头节点的链表反转 |
通关 |
| 不带虚拟节点的链表反转 |
通关 |
题目
【LeetCode 206】：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
参考资料
链表3.透彻理解链表反转以及拓展问题
链表6：大厂如何考链表反转
【基础】建立虚拟头节点辅助反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public ListNode reverseList(ListNode head) {
ListNode L = new ListNode(-1);
L.next = head;
L.next = null;
ListNode p = head;
while (p != null) {
ListNode q = p.next;
p.next = L.next;
L.next = p;
p = q;
}
return L.next;
}
|
【推荐】直接操作链表实现反转
面试常考：直接操作指针进行反转
反转前后的结构和指针位置：
算法思想
cur 指向旧链表的首节点prev 表示已经调整好的新链表的表头next 表示下一个需要调整的节点cur 和 prev 是两个表的表头，移动过程中 cur 经过一次中间状态后，又重新变成两个链表的表头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
|
递归反转
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
|
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
|
链表专题Ⅱ—反转强化
通关进度
| 题目 |
说明 |
| 指定区间反转 |
通关 |
| 两两交换链表中的节点 |
通关 |
| 单链表加 1 |
通关 |
| 链表加法 |
通关 |
指定区间反转
问题
【LeetCode 92】：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
穿针引线
以下图中黄色区域的链表反转为栗：
反转 left 到 right 部分以后，再拼接起来。此外，还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：
- 先将待反转的区域反转
- 把
pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。
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
| public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
ListNode leftNode = pre.next;
ListNode curr = rightNode.next;
pre.next = null;
rightNode.next = null;
reverseLinkedList(leftNode);
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
}
public void reverseLinkedList(ListNode head) {
ListNode L = new ListNode(0);
L.next = head;
ListNode p = head;
L.next = null;
while (p != null) {
ListNode q = p.next;
p.next = L.next;
L.next = p;
p = q;
}
}
|
头插法
算法思想
在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置
使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：
curr：指向待反转区域的第一个节点 left；next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。
第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。
- 先将
curr 的下一个节点记录为 next；
- 执行操作 ①：把
curr 的下一个节点指向 next 的下一个节点；
- 执行操作 ②：把
next 的下一个节点指向 pre 的下一个节点；
- 执行操作 ③：把
pre 的下一个节点指向 next。
第 1 步完成以后「拉直」的效果如下：
第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。
第 2 步完成以后「拉直」的效果如下：
第 3 步，同理。
第 3 步完成以后「拉直」的效果如下：
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
| public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < right - left; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
}
|
两两交换链表中的节点
问题
【LeetCode 24】：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
迭代
创建哑结点 dummyHead，令 dummyHead.next = head。令 temp 表示当前到达的节点，初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。
如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得 temp 后面的两个节点 node1 和 node2，通过更新节点的指针关系实现两两交换节点。
具体而言，交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1，因此需要进行如下操作。
1
2
3
| temp.next = node2
node1.next = node2.next
node2.next = node1
|
完成上述操作之后，节点关系即变成 temp -> node2 -> node1。再令 temp = node1，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。
两两交换链表中的节点之后，新的链表的头节点是 dummyHead.next，返回新的链表的头节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}
|
头插法
算法思想
计算链表长度 len，根据链表长度 len 划分交换次数，然后进行 len/2 次链表交换操作即可
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
|
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
int length = 0;
ListNode cur = head;
while (cur != null) {
length++;
cur = cur.next;
}
ListNode tail = dummyHead;
ListNode next = dummyHead;
for (int i = 0; i < length / 2; i++) {
cur = tail.next;
ListNode temp = cur;
tail.next = null;
for (int j = 0; j < 2; j++) {
next = cur.next;
cur.next = tail.next;
tail.next = cur;
cur = next;
}
tail = temp;
tail.next = cur;
}
return dummyHead.next;
}
|
单链表加 1
问题
【LeetCode 369】：用一个非空单链表表示一个非负整数，然后将这个整数加一。你可以假设这个整数除了 0 本身，没有任何前导的 0。这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
算法思想
加法计算是低位至高位，而本题是高位在链表头部，低位在链表尾部。本题可以采用栈或者链表反转实现。
基于栈
遍历链表然后入栈，从栈中弹出栈顶数字 digit，然后考虑进位相加
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
| public ListNode plusOne(ListNode head) {
Stack<Integer> stack = new Stack<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
int carry = 0;
ListNode dummyNode = new ListNode(0);
int adder = 1;
while (!stack.isEmpty() || carry > 0) {
int digit = stack.empty() ? 0 : stack.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummyNode.next;
dummyNode.next = cur;
adder = 0;
}
return dummyNode.next;
}
|
基于链表反转
将原始链表进行反转，然后进行（考虑进位的）加一操作，完成操作后重新反转链表得到结果
链表加法
问题
【LeetCode 445】：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
算法思想
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
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
| public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode dummyNode = new ListNode(0);
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int a = stack1.isEmpty() ? 0 : stack1.pop();
int b = stack2.isEmpty() ? 0 : stack2.poll();
int sum = a + b + carry;
carry = sum / 10;
sum %= 10;
ListNode currNode = new ListNode(sum);
currNode.next = dummyNode.next;
dummyNode.next = currNode;
}
return dummyNode.next;
}
|
链表专题Ⅱ— K 组反转
问题
【LeetCode 25】：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
头插法
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
| public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
int length = 0;
ListNode cur = head;
while (cur != null) {
length++;
cur = cur.next;
}
ListNode tail = dummyHead;
ListNode next = dummyHead;
for (int i = 0; i < length / k; i++) {
cur = tail.next;
ListNode temp = cur;
tail.next = null;
for (int j = 0; j < k; j++) {
next = cur.next;
cur.next = tail.next;
tail.next = cur;
cur = next;
}
tail = temp;
tail.next = cur;
}
return dummyHead.next;
}
|
穿针引线
由于分组反转，我们可以将其分成 已经反转、正在反转、未反转的三个部分，同时为处理好节点关系，我们新建虚拟节点。
之后直接遍历，根据是否为 K 个找到四个关键位置，并使用 pre、begin、end 和 next 进行标记，如图所示：
反转蓝色部分：
反转完成后，将链表恢复，然后调整指针指向：
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
| public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
ListNode end = dummyNode;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode begin = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(begin);
begin.next = next;
pre = begin;
end = pre;
}
return dummyNode.next;
}
public ListNode reverse(ListNode head) {
ListNode L = new ListNode(0);
L.next = head;
ListNode curr = head;
L.next = null;
while(curr != null) {
ListNode next = curr.next;
curr.next = L.next;
L.next = curr;
curr = next;
}
return L.next;
}
|
