第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0092. 反转链表 II

题目地址(92. 反转链表 II)

题目描述

1
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
2
3
说明:
4
1 ≤ m ≤ n ≤ 链表长度。
5
6
示例:
7
8
输入: 1->2->3->4->5->NULL, m = 2, n = 4
9
输出: 1->4->3->2->5->NULL
Copied!

前置知识

  • 链表

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路(四点法)

这道题和206.reverse-linked-list 有点类似,并且这道题是 206 的升级版。 让我们反转某一个区间,而不是整个链表,我们可以将 206 看作本题的特殊情况(special case)。
核心在于取出需要反转的这一小段链表,反转完后再插入到原先的链表中。
以本题为例:
反转的是 2,3,4 这三个点,那么我们可以先取出 2,用 cur 指针指向 2,然后当取出 3 的时候,我们将 3 指向 2 的,把 cur 指针前移到 3,依次类推,到 4 后停止,这样我们得到一个新链表 4->3->2, cur 指针指向 4。
对于原链表来说,有两个点的位置很重要,需要用指针记录下来,分别是 1 和 5,把新链表插入的时候需要这两个点的位置。用 pre 指针记录 1 的位置当 4 结点被取走后,5 的位置需要记下来
这样我们就可以把反转后的那一小段链表加入到原链表中
92.reverse-linked-list-ii
(图片来自网络)
  • 首先我们直接返回 head 是不行的。 当 m 不等于 1 的时候是没有问题的,但只要 m 为 1,就会有问题。
  • 其次如果链表商都小于 4 的时候,p1,p2,p3,p4 就有可能为空。为了防止 NPE,我们也要充分地判空。
1
class Solution:
2
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
3
pre = None
4
cur = head
5
i = 0
6
p1 = p2 = p3 = p4 = None
7
# 一坨逻辑
8
if p1:
9
p1.next = p3
10
else:
11
dummy.next = p3
12
if p2:
13
p2.next = p4
14
return head
Copied!
如上代码是不可以的,我们考虑使用 dummy 节点。
1
class Solution:
2
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
3
pre = None
4
cur = head
5
i = 0
6
p1 = p2 = p3 = p4 = None
7
dummy = ListNode(0)
8
dummy.next = head
9
# 一坨逻辑
10
if p1:
11
p1.next = p3
12
else:
13
dummy.next = p3
14
if p2:
15
p2.next = p4
16
17
return dummy.next
Copied!
关于链表反转部分, 顺序比较重要,我们需要:
  • 先 cur.next = pre
  • 再 更新 p2 和 p2.next(其中要设置 p2.next = None,否则会互相应用,造成无限循环)
  • 最后更新 pre 和 cur
上述的顺序不能错,不然会有问题。原因就在于p2.next = None,如果这个放在最后,那么我们的 cur 会提前断开。
1
while cur:
2
i += 1
3
if i == m - 1:
4
p1 = cur
5
next = cur.next
6
if m < i <= n:
7
cur.next = pre
8
9
if i == m:
10
p2 = cur
11
p2.next = None
12
13
if i == n:
14
p3 = cur
15
16
if i == n + 1:
17
p4 = cur
18
19
pre = cur
20
cur = next
Copied!

关键点解析

  • 四点法
  • 链表的基本操作
  • 考虑特殊情况 m 是 1 或者 n 是链表长度的情况,我们可以采用虚拟节点 dummy 简化操作
  • 用四个变量记录特殊节点, 然后操作这四个节点使之按照一定方式连接即可。
  • 注意更新 current 和 pre 的位置, 否则有可能出现溢出

代码

我把这个方法称为 四点法
语言支持:JS, Python3, CPP
JavaScript Code:
1
/*
2
* @lc app=leetcode id=92 lang=javascript
3
*
4
* [92] Reverse Linked List II
5
*
6
* https://leetcode.com/problems/reverse-linked-list-ii/description/
7
*/
8
/**
9
* Definition for singly-linked list.
10
* function ListNode(val) {
11
* this.val = val;
12
* this.next = null;
13
* }
14
*/
15
/**
16
* @param {ListNode} head
17
* @param {number} m
18
* @param {number} n
19
* @return {ListNode}
20
*/
21
var reverseBetween = function (head, m, n) {
22
// 虚拟节点,简化操作
23
const dummyHead = {
24
next: head,
25
};
26
27
let cur = dummyHead.next; // 当前遍历的节点
28
let pre = cur; // 因为要反转,因此我们需要记住前一个节点
29
let index = 0; // 链表索引,用来判断是否是特殊位置(头尾位置)
30
31
// 上面提到的四个特殊节点
32
let p1 = (p2 = p3 = p4 = null);
33
34
while (cur) {
35
const next = cur.next;
36
index++;
37
38
// 对 (m - n) 范围内的节点进行反转
39
if (index > m && index <= n) {
40
cur.next = pre;
41
}
42
43
// 下面四个if都是边界, 用于更新四个特殊节点的值
44
if (index === m - 1) {
45
p1 = cur;
46
}
47
if (index === m) {
48
p2 = cur;
49
}
50
51
if (index === n) {
52
p3 = cur;
53
}
54
55
if (index === n + 1) {
56
p4 = cur;
57
}
58
59
pre = cur;
60
61
cur = next;
62
}
63
64
// 两个链表合并起来
65
(p1 || dummyHead).next = p3; // 特殊情况需要考虑
66
p2.next = p4;
67
68
return dummyHead.next;
69
};
Copied!
Python Code:
1
class Solution:
2
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
3
if not head.next or n == 1:
4
return head
5
dummy = ListNode()
6
dummy.next = head
7
pre = None
8
cur = head
9
i = 0
10
p1 = p2 = p3 = p4 = None
11
while cur:
12
i += 1
13
next = cur.next
14
if m < i <= n:
15
cur.next = pre
16
if i == m - 1:
17
p1 = cur
18
if i == m:
19
p2 = cur
20
if i == n:
21
p3 = cur
22
if i == n + 1:
23
p4 = cur
24
pre = cur
25
cur = next
26
if not p1:
27
dummy.next = p3
28
else:
29
p1.next = p3
30
p2.next = p4
31
return dummy.next
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。