链表
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
"""
使用双指针法找出两个链表的相交节点
思路：
- 如果两个链表相交，相交之后的节点都是相同的
- 链表 A 长度 = m，链表 B 长度 = n
- 让指针 pA 先走完 A 再走 B，指针 pB 先走完 B 再走 A
- 如果相交：pA 和 pB 会在相交节点相遇（走的总长度都是 m + n - 相交部分长度）
- 如果不相交：pA 和 pB 会同时走到 None 并退出
- 时间 O(m+n)，空间 O(1)
"""
if not headA or not headB:
return None
pA = headA
pB = headB
# 两个指针会走相同的步数（m+n），要么相遇要么同时到 None
while pA != pB:
# pA 走完 A 就走 B
pA = pA.next if pA else headB
# pB 走完 B 就走 A
pB = pB.next if pB else headA
return pA
# 测试用例
def build_linked_list(values, pos=-1):
"""根据数组构建链表，pos 指定相交位置（0-indexed）"""
if not values:
return None
head = ListNode(values[0])
current = head
nodes = [head]
for i in range(1, len(values)):
current.next = ListNode(values[i])
current = current.next
nodes.append(current)
# 设置相交点
if pos >= 0 and pos < len(nodes):
current.next = nodes[pos]
return head, nodes[0] if nodes else None
# 示例1: 相交于节点 8
headA, _ = build_linked_list([4, 1, 8, 4, 5])
headB, _ = build_linked_list([5, 6, 1, 8, 4, 5], pos=3)
intersect = Solution().getIntersectionNode(headA, headB)
assert intersect.val == 8 # 相交节点值为 8
# 示例2: 相交于节点 2
headA, _ = build_linked_list([1, 9, 1, 2, 4])
headB, _ = build_linked_list([3, 2, 4], pos=1)
intersect = Solution().getIntersectionNode(headA, headB)
assert intersect.val == 2 # 相交节点值为 2
# 示例3: 不相交
headA, _ = build_linked_list([2, 6, 4])
headB, _ = build_linked_list([1, 5])
assert Solution().getIntersectionNode(headA, headB) is None
# 手动推导（相交情况）：
# 链表 A: 4 -> 1 -> 8 -> 4 -> 5 (长度 m=5)
# 链表 B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 (长度 n=6)
#
# 初始：pA=4, pB=5
# 第1步：pA=1, pB=6
# 第2步：pA=8, pB=1
# 第3步：pA=4, pB=8 （pA走完A，切换到B的头；pB继续）
# 第4步：pA=5, pB=4
# 第5步：pA=5(B尾)->None->5(B头), pB=8
# 第6步：pA=6, pB=4
# 第7步：pA=1, pB=5
# 第8步：pA=8, pB=None->4(A头) （pB走完B，切换到A的头）
# 第9步：pA=4, pB=1
# 第10步：pA=5, pB=8 （此时 pA 和 pB 距离相交节点都是 2 步）
# 第11步：pA=8, pB=4
# 第12步：pA=4, pB=5
# 第13步：pA=5, pB=None->5(B头) （都走完自己的链表，切换）
# ...继续下去，pA 和 pB 会相遇于 8
#
# 实际上，由于 A 末尾的 4->5 和 B 的 5->6->1->8->4->5 共享后缀
# 两指针走过相同距离后必定在 8 相遇
|
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList_iterative(self, head: ListNode) -> ListNode:
"""
方法一：迭代（双指针）
思路：
- 使用 prev 和 curr 两个指针
- prev 初始为 None，curr 初始为 head
- 遍历链表，逐个将 curr.next 指向 prev（翻转指针）
- 最后 prev 就是新的头节点
- 时间 O(n)，空间 O(1)
"""
prev = None
curr = head
while curr:
next_node = curr.next # 1. 先保存下一个节点
curr.next = prev # 2. 翻转当前节点的指针
prev = curr # 3. prev 右移
curr = next_node # 4. curr 右移
return prev # prev 是新的头节点
def reverseList_recursive(self, head: ListNode) -> ListNode:
"""
方法二：递归
思路：
- 递归到链表末尾
- 从后往前翻转指针
- base case: 空链表或只有一个节点，直接返回
- 递归假设：假设 reverseList(head.next) 已经反转了后面的链表
- 当前层：让 head.next.next = head，完成当前节点的翻转
- 时间 O(n)，空间 O(n)（递归栈）
"""
# base case
if not head or not head.next:
return head
# 递归：反转以 head.next 为头的后半部分
new_head = self.reverseList_recursive(head.next)
# 翻转当前节点的指针
head.next.next = head # 让下一个节点的 next 指向当前节点
head.next = None # 当前节点的 next 置空
return new_head
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 迭代法测试
head = build_list([1, 2, 3, 4, 5])
result = Solution().reverseList_iterative(head)
assert to_list(result) == [5, 4, 3, 2, 1]
head = build_list([1, 2])
result = Solution().reverseList_iterative(head)
assert to_list(result) == [2, 1]
head = build_list([])
result = Solution().reverseList_iterative(head)
assert to_list(result) == []
# 递归法测试
head = build_list([1, 2, 3, 4, 5])
result = Solution().reverseList_recursive(head)
assert to_list(result) == [5, 4, 3, 2, 1]
head = build_list([1])
result = Solution().reverseList_recursive(head)
assert to_list(result) == [1]
# 手动推导（迭代法）[1,2,3,4,5]：
# 初始: prev=None, curr=1
# 第1步: next=2, curr.next=None, prev=1, curr=2 -> None<-1
# 第2步: next=3, curr.next=1, prev=2, curr=3 -> None<-1<-2
# 第3步: next=4, curr.next=2, prev=3, curr=4 -> None<-1<-2<-3
# 第4步: next=5, curr.next=3, prev=4, curr=5 -> None<-1<-2<-3<-4
# 第5步: next=None, curr.next=4,prev=5, curr=None -> None<-1<-2<-3<-4<-5
# 返回 prev=5
# 结果: 5->4->3->2->1
|
回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
输入：head = [1,2,2,1]
输出：true
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
"""
使用快慢指针找到链表中点，同时反转前半部分，然后比较
思路：
- 使用快慢指针：slow 一次走一步，fast 一次走两步
- 当 fast 到达末尾时，slow 正好到中点
- 在慢指针前进的过程中反转前半部分链表
- 最后从中点开始比较前半部分（已反转）和后半部分
- 时间 O(n)，空间 O(1)
例如 [1,2,2,1]:
- 找到中点后，前半部分 [1,2] 反转成 [2,1]
- 后半部分是 [2,1]，逐一比较即可
"""
if not head or not head.next:
return True
# 第一步：找到链表中点，同时反转前半部分
slow = head
fast = head
prev = None # 用于反转
while fast and fast.next:
fast = fast.next.next # fast 走两步
# 翻转前半部分
next_node = slow.next # 保存 slow 的下一个节点
slow.next = prev # 翻转指针
prev = slow # prev 右移
slow = next_node # slow 右移到中点
# 如果 fast 不为空，说明链表有奇数个节点，slow 需要再走一步跳过中间节点
if fast:
slow = slow.next
# 此时 prev 指向反转后的前半部分头，slow 指向后半部分头
# 比较两部分
while prev and slow:
if prev.val != slow.val:
return False
prev = prev.next
slow = slow.next
return True
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
# 示例1: [1,2,2,1] 是回文
assert Solution().isPalindrome(build_list([1, 2, 2, 1])) == True
# 示例2: [1,2] 不是回文
assert Solution().isPalindrome(build_list([1, 2])) == False
# 更多测试
assert Solution().isPalindrome(build_list([1])) == True
assert Solution().isPalindrome(build_list([1, 2, 3, 2, 1])) == True
assert Solution().isPalindrome(build_list([1, 2, 3, 3, 2, 1])) == True
assert Solution().isPalindrome(build_list([1, 2, 3, 4, 2, 1])) == False
assert Solution().isPalindrome(build_list([])) == True
# 手动推导 [1,2,2,1]：
# 初始: slow=1, fast=1, prev=None
# 第1次循环:
# fast = 3 (走两步)
# next_node = 2, slow.next = None (翻转: 1->None), prev=1, slow=2
# 第2次循环:
# fast = None (走到末尾)
# next_node = 2, slow.next = 1 (翻转: 2->1), prev=2, slow=2
# fast=None，无需调整 slow
# 比较:
# prev=2 vs slow=2 (从后半部分头) -> 相等
# prev=1 vs slow=1 -> 相等
# prev=None, slow=None -> 结束
# 结果: True
|
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
"""
使用快慢指针判断链表中是否有环
思路：
- 快指针 fast 每次走两步，慢指针 slow 每次走一步
- 如果链表有环：fast 和 slow 最终会在环内相遇
- 如果链表无环：fast 会先到达末尾（None）
- 时间 O(n)，空间 O(1)
为什么有环时一定会相遇？
- 假设环长为 L，慢指针进入环时，快指针已在环内某个位置
- 设此时快慢指针的距离为 d（0 <= d < L）
- 每一步，快慢指针距离减少 1
- 经过 d 步后相遇
"""
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
if slow == fast: # 相遇，说明有环
return True
# fast 走到末尾，说明无环
return False
# 测试用例
def build_list_with_cycle(values, pos):
"""构建带环链表，pos 是环入口的索引（0-indexed），-1 表示无环"""
if not values:
return None, None
nodes = [ListNode(v) for v in values]
head = nodes[0]
for i in range(len(values) - 1):
nodes[i].next = nodes[i + 1]
if pos >= 0 and pos < len(nodes):
nodes[-1].next = nodes[pos]
return head, nodes[pos] if pos >= 0 else None
# 示例1: 有环 (pos=1)
head, _ = build_list_with_cycle([3, 2, 0, -4], 1)
assert Solution().hasCycle(head) == True
# 示例2: 有环 (pos=0)
head, _ = build_list_with_cycle([1, 2], 0)
assert Solution().hasCycle(head) == True
# 示例3: 无环 (pos=-1)
head, _ = build_list_with_cycle([1], -1)
assert Solution().hasCycle(head) == False
# 无环情况
head, _ = build_list_with_cycle([1, 2, 3, 4, 5], -1)
assert Solution().hasCycle(head) == False
# 手动推导有环链表 [3,2,0,-4]，pos=1（环入口在节点2）：
# 链表结构: 3 -> 2 -> 0 -> -4 --+
# ^ |
# +---------------+
#
# 初始: slow=3, fast=3
# 第1步: slow=2, fast=0 (fast走两步)
# slow != fast，继续
# 第2步: slow=-4, fast=3
# slow != fast，继续
# 第3步: slow=0, fast=-4
# slow != fast，继续
# 第4步: slow=2, fast=2 (相遇！)
# slow == fast，返回 True
#
# 手动推导无环链表 [1,2,3]：
# 初始: slow=1, fast=1
# 第1步: slow=2, fast=3
# slow != fast，继续
# 第2步: fast.next=None，退出循环
# 返回 False
|
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
进阶：你是否可以使用 O(1) 空间解决此题？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
"""
使用快慢指针找到相遇点，然后从相遇点和头节点同时出发，再次相遇点即为环入口
思路：
- 第一步：快慢指针找到相遇点（如果有环）
- 第二步：从相遇点和头节点同时出发，每次走一步，再次相遇点就是环入口
数学证明：
- 设链表头到环入口距离为 a
- 环入口到相遇点距离为 b
- 相遇点到环入口距离为 c（环长 L = b + c）
- 慢指针路程 = a + b
- 快指针路程 = a + b + k*L（k >= 1）
- 快指针速度是慢指针2倍：2(a+b) = a + b + k*L
- 得 a = (k-1)*L + c = c + (k-1)*L
- 所以从相遇点出发走 a 步，与从头节点出发走 a 步，会在环入口相遇
- 时间 O(n)，空间 O(1)
"""
if not head or not head.next:
return None
# 第一步：快慢指针找相遇点
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
# 如果没有相遇点，说明无环
if not fast or not fast.next:
return None
# 第二步：从相遇点和头节点同时出发，找环入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
# 测试用例
def build_list_with_cycle(values, pos):
"""构建带环链表，pos 是环入口的索引（0-indexed），-1 表示无环"""
if not values:
return None, None
nodes = [ListNode(v) for v in values]
head = nodes[0]
for i in range(len(values) - 1):
nodes[i].next = nodes[i + 1]
if pos >= 0 and pos < len(nodes):
nodes[-1].next = nodes[pos]
return head, nodes[pos] if pos >= 0 else None
# 示例1: 环入口在索引1（节点2）
head, expected = build_list_with_cycle([3, 2, 0, -4], 1)
result = Solution().detectCycle(head)
assert result == expected
assert result.val == 2
# 示例2: 环入口在索引0（节点1）
head, expected = build_list_with_cycle([1, 2], 0)
result = Solution().detectCycle(head)
assert result == expected
assert result.val == 1
# 示例3: 无环
head, _ = build_list_with_cycle([1], -1)
assert Solution().detectCycle(head) is None
# 更多测试
head, _ = build_list_with_cycle([1, 2, 3, 4, 5], -1)
assert Solution().detectCycle(head) is None
# 手动推导链表 [3,2,0,-4]，pos=1（环入口在节点2）：
# 链表结构: 3 -> 2 -> 0 -> -4 --+
# ^ |
# +---------------+
# a=1 (3到2的距离), b=3 (2到-4的距离), c=1 (-4到2的距离)
# 环长 L = b + c = 3 + 1 = 4
#
# 第一步：快慢指针找相遇点
# 初始: slow=3, fast=3
# 第1次: slow=2, fast=0
# 第2次: slow=-4, fast=3
# 第3次: slow=0, fast=-4
# 第4次: slow=2, fast=2 (相遇！相遇点距离环入口b=3)
#
# 第二步：从头节点和相遇点同时出发
# slow=3(头), fast=2(相遇点)
# slow=2, fast=0 -> slow=2, fast=-4 -> slow=0, fast=2 -> slow=-4, fast=-4 (相遇！)
# 相遇点=-4？不对，应该是2...
#
# 重新分析：
# 相遇点应该是0，slow=2, fast=0
# slow=0, fast=2
# slow=2, fast=-4
# slow=-4, fast=0
# slow=0, fast=-4
# slow=-4, fast=2
# slow=2, fast=0 ...实际上相遇点应该在环入口2
#
# 正确推导：
# 从相遇点(0)到环入口(2)的距离是 c=1
# 从头节点(3)到环入口(2)的距离是 a=1
# 所以第二次遍历：
# slow=3, fast=0 -> 相遇？不
# slow=2, fast=-4 -> 相遇？不
# slow=0, fast=2 -> 相遇！返回节点2
#
# 结果：环入口是节点2
|
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
l1 和 l2 均按 非递减顺序 排列
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
"""
使用虚拟头节点合并两个有序链表
思路：
- 创建虚拟头节点 dummy，简化边界处理
- 使用双指针比较两个链表的当前节点
- 每次选择较小的节点接到结果链表
- 最后处理剩余部分
- 时间 O(m+n)，空间 O(1)
"""
dummy = ListNode(-1) # 虚拟头节点
current = dummy
# 同时遍历两个链表，选择较小的节点
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# 处理剩余部分（其中一个链表已遍历完）
current.next = list1 if list1 else list2
return dummy.next
def mergeTwoLists_recursive(self, list1: ListNode, list2: ListNode) -> ListNode:
"""
递归版本
思路：
- base case: 其中一个链表为空，返回另一个
- 递归假设：假设 mergeTwoLists(list1.next, list2) 已处理好
- 当前层：比较 list1 和 list2 的头，选择较小的作为新头
- 时间 O(m+n)，空间 O(m+n)（递归栈）
"""
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists_recursive(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists_recursive(list1, list2.next)
return list2
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: [1,2,4] 和 [1,3,4] 合并为 [1,1,2,3,4,4]
list1 = build_list([1, 2, 4])
list2 = build_list([1, 3, 4])
result = Solution().mergeTwoLists(list1, list2)
assert to_list(result) == [1, 1, 2, 3, 4, 4]
# 示例2: [] 和 [] 合并为 []
list1 = build_list([])
list2 = build_list([])
result = Solution().mergeTwoLists(list1, list2)
assert to_list(result) == []
# 示例3: [] 和 [0] 合并为 [0]
list1 = build_list([])
list2 = build_list([0])
result = Solution().mergeTwoLists(list1, list2)
assert to_list(result) == [0]
# 更多测试
assert to_list(Solution().mergeTwoLists(build_list([1]), build_list([]))) == [1]
assert to_list(Solution().mergeTwoLists(build_list([]), build_list([1]))) == [1]
assert to_list(Solution().mergeTwoLists(build_list([1, 3, 5]), build_list([2, 4, 6]))) == [1, 2, 3, 4, 5, 6]
# 手动推导 [1,2,4] 和 [1,3,4]：
# dummy -> ? -> ...
# 初始: list1=1, list2=1, 1<=1, 选择list1
# dummy -> 1 -> ?
# list1 = 2
# 第1次: list1=2, list2=1, 2>1, 选择list2
# dummy -> 1 -> 1 -> ?
# list2 = 3
# 第2次: list1=2, list2=3, 2<=3, 选择list1
# dummy -> 1 -> 1 -> 2 -> ?
# list1 = 4
# 第3次: list1=4, list2=3, 4>3, 选择list2
# dummy -> 1 -> 1 -> 2 -> 3 -> ?
# list2 = 4
# 第4次: list1=4, list2=4, 4<=4, 选择list1
# dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> ?
# list1 = 4(None)
# list1为空，连接list2剩余: 4
# 最终: 1 -> 1 -> 2 -> 3 -> 4 -> 4
|
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
题目数据保证列表表示的数字不含前导零
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
"""
模拟按位相加，注意进位
思路：
- 同时遍历两个链表，按位相加
- 当前位的和 = l1.val + l2.val + carry(进位)
- 新节点的值 = 和 % 10
- 新的进位 = 和 // 10
- 如果最后还有进位，需要添加一个新节点
- 时间 O(max(m,n))，空间 O(max(m,n))
例如：342 + 465 = 807
链表: 2->4->3 和 5->6->4
从右往左加:
2+5=7, 进位0 -> 7
4+6=10, 进位1 -> 0
3+4+1=8, 进位0 -> 8
结果: 7->0->8
"""
dummy = ListNode(0) # 虚拟头节点
current = dummy
carry = 0 # 进位
while l1 or l2 or carry:
# 获取当前位的值（如果链表已遍历完则为0）
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 计算当前位的和
total = val1 + val2 + carry
carry = total // 10 # 新的进位
current.next = ListNode(total % 10) # 当前位的值
# 移动指针
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: 342 + 465 = 807
l1 = build_list([2, 4, 3])
l2 = build_list([5, 6, 4])
assert to_list(Solution().addTwoNumbers(l1, l2)) == [7, 0, 8]
# 示例2: 0 + 0 = 0
l1 = build_list([0])
l2 = build_list([0])
assert to_list(Solution().addTwoNumbers(l1, l2)) == [0]
# 示例3: 9999999 + 9999 = 10009998
l1 = build_list([9, 9, 9, 9, 9, 9, 9])
l2 = build_list([9, 9, 9, 9])
assert to_list(Solution().addTwoNumbers(l1, l2)) == [8, 9, 9, 9, 0, 0, 0, 1]
# 更多测试
l1 = build_list([5])
l2 = build_list([5])
assert to_list(Solution().addTwoNumbers(l1, l2)) == [0, 1]
# 手动推导 l1=[2,4,3], l2=[5,6,4]（342 + 465）：
# dummy -> ? -> ? -> ?
#
# 第1位: 2+5=7, carry=0 -> 节点7
# dummy -> 7
#
# 第2位: 4+6=10, carry=1 -> 节点0
# dummy -> 7 -> 0
#
# 第3位: 3+4+1=8, carry=0 -> 节点8
# dummy -> 7 -> 0 -> 8
#
# 第4位: l1=None, l2=None, carry=0，结束
#
# 结果: 7 -> 0 -> 8 (即 807)
|
删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
进阶：你能尝试使用一趟扫描实现吗？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
"""
使用快慢指针，一趟扫描删除倒数第 N 个节点
思路：
- 创建虚拟头节点，简化删除头节点的处理
- 快指针先走 n+1 步，然后快慢指针同时走
- 当快指针到达末尾时，慢指针正好在待删除节点的前一个位置
- 时间 O(L)，空间 O(1)
图解（删除倒数第2个节点）：
1 -> 2 -> 3 -> 4 -> 5
|<- n=2 ->|
快指针先走 n+1=3 步，然后一起走：
初始: fast=1, slow=dummy
快走3步: fast=4, slow=dummy
同时走: fast=5, slow=2
同时走: fast=None, slow=3
删除 slow.next（即节点4）
"""
dummy = ListNode(0)
dummy.next = head
# 快指针先走 n+1 步
fast = dummy
for i in range(n + 1):
fast = fast.next
# 快慢指针同时走，直到 fast 到达末尾
slow = dummy
while fast:
fast = fast.next
slow = slow.next
# 此时 slow 指向待删除节点的前一个节点
slow.next = slow.next.next
return dummy.next
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: 删除倒数第2个 [1,2,3,4,5] -> [1,2,3,5]
head = build_list([1, 2, 3, 4, 5])
result = Solution().removeNthFromEnd(head, 2)
assert to_list(result) == [1, 2, 3, 5]
# 示例2: 删除倒数第1个 [1] -> []
head = build_list([1])
result = Solution().removeNthFromEnd(head, 1)
assert to_list(result) == []
# 示例3: 删除倒数第1个 [1,2] -> [1]
head = build_list([1, 2])
result = Solution().removeNthFromEnd(head, 1)
assert to_list(result) == [1]
# 更多测试
head = build_list([1, 2, 3])
result = Solution().removeNthFromEnd(head, 3)
assert to_list(result) == [2, 3]
head = build_list([1, 2])
result = Solution().removeNthFromEnd(head, 2)
assert to_list(result) == [2]
# 手动推导 [1,2,3,4,5]，n=2（删除倒数第2个，即节点4）：
#
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
#
# 第1步：快指针先走 n+1=3 步
# fast=0 -> 1 -> 2 -> 3 -> None
# slow 仍在 dummy
#
# 第2步：快慢指针同时走
# fast=4, slow=1
# fast=5, slow=2
# fast=None, slow=3
#
# 第3步：删除 slow.next（即节点4）
# slow.next = slow.next.next
# 3 -> 5
#
# 结果: 1 -> 2 -> 3 -> 5
|
两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,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
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
"""
两两交换相邻节点，使用虚拟头节点简化处理
思路：
- 创建虚拟头节点 dummy，简化头节点交换的处理
- 每次处理一对节点：pre -> node1 -> node2 -> node2.next
- 交换后：pre -> node2 -> node1 -> node2.next
- 然后移动 pre 到 node1，继续处理下一对
- 时间 O(n)，空间 O(1)
图解：
交换前: pre -> 1 -> 2 -> 3 -> 4 -> None
交换后: pre -> 2 -> 1 -> 3 -> 4 -> None
"""
dummy = ListNode(0)
dummy.next = head
pre = dummy # pre 指向已处理部分和待处理部分的边界
while pre.next and pre.next.next:
# 取两个待交换的节点
node1 = pre.next
node2 = pre.next.next
# 交换：pre -> node2 -> node1
node1.next = node2.next # 1 -> 3
node2.next = node1 # 2 -> 1
pre.next = node2 # pre -> 2
# 移动 pre 到下一对待交换位置的前一个节点（即 node1）
pre = node1
return dummy.next
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: [1,2,3,4] -> [2,1,4,3]
head = build_list([1, 2, 3, 4])
result = Solution().swapPairs(head)
assert to_list(result) == [2, 1, 4, 3]
# 示例2: [] -> []
head = build_list([])
result = Solution().swapPairs(head)
assert to_list(result) == []
# 示例3: [1] -> [1]
head = build_list([1])
result = Solution().swapPairs(head)
assert to_list(result) == [1]
# 更多测试
assert to_list(Solution().swapPairs(build_list([1, 2]))) == [2, 1]
assert to_list(Solution().swapPairs(build_list([1, 2, 3]))) == [2, 1, 3]
assert to_list(Solution().swapPairs(build_list([1, 2, 3, 4, 5]))) == [2, 1, 4, 3, 5]
# 手动推导 [1,2,3,4]：
# dummy -> 1 -> 2 -> 3 -> 4 -> None
#
# 初始: pre=dummy, node1=1, node2=2
# 交换第1对:
# node1.next = node2.next -> 1 -> 3
# node2.next = node1 -> 2 -> 1 -> 3
# pre.next = node2 -> dummy -> 2 -> 1 -> 3
# pre = node1 -> pre 指向节点1
#
# 结果中间状态: dummy -> 2 -> 1 -> 3 -> 4 -> None
# pre
#
# 继续遍历:
# pre.next = 1, pre.next.next = 3
# node1 = 1, node2 = 3
# 交换第2对:
# node1.next = node2.next -> 1 -> 4
# node2.next = node1 -> 3 -> 1 -> 4
# pre.next = node2 -> 1 -> 3 -> 1 -> 4
# pre = node1 -> pre 指向节点1
#
# 结果: dummy -> 2 -> 1 -> 4 -> 3 -> None
# 最终: 2 -> 1 -> 4 -> 3
|
K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
"""
K 个一组翻转链表
思路：
- 遍历链表，找到每 k 个节点作为一组
- 对每组进行局部翻转
- 使用虚拟头节点简化头节点处理
- 时间 O(n)，空间 O(1)
步骤：
1. 检查剩余节点数是否够 k 个，不够则不翻转
2. 反转这 k 个节点
3. 连接翻转前后的部分
4. 移动到下一组继续处理
"""
dummy = ListNode(0)
dummy.next = head
pre = dummy # pre 指向待翻转组的前一个节点
end = dummy # end 指向待翻转组的最后一个节点
while end.next:
# 1. 让 end 走 k 步，检查是否有 k 个节点
for i in range(k):
end = end.next
if not end: # 节点数不够 k 个，结束
break
if not end: # 节点数不够
break
# 2. 记录待翻转部分的首尾节点
start = pre.next
next_group = end.next
# 3. 断开连接，准备翻转
end.next = None
# 4. 翻转这一组
pre.next = self.reverse(start)
# 5. 连接翻转后的部分
start.next = next_group
# 6. 移动 pre 和 end 到下一组的前一个位置
pre = start
end = pre
return dummy.next
def reverse(self, head: ListNode) -> ListNode:
"""
反转链表，返回新的头节点
"""
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: k=2, [1,2,3,4,5] -> [2,1,4,3,5]
head = build_list([1, 2, 3, 4, 5])
result = Solution().reverseKGroup(head, 2)
assert to_list(result) == [2, 1, 4, 3, 5]
# 示例2: k=3, [1,2,3,4,5] -> [3,2,1,4,5]
head = build_list([1, 2, 3, 4, 5])
result = Solution().reverseKGroup(head, 3)
assert to_list(result) == [3, 2, 1, 4, 5]
# 更多测试
assert to_list(Solution().reverseKGroup(build_list([1]), 2)) == [1]
assert to_list(Solution().reverseKGroup(build_list([1, 2]), 2)) == [2, 1]
assert to_list(Solution().reverseKGroup(build_list([1, 2, 3]), 2)) == [2, 1, 3]
assert to_list(Solution().reverseKGroup(build_list([1, 2, 3, 4, 5, 6, 7, 8]), 3)) == [3, 2, 1, 6, 5, 4, 8, 7]
# 手动推导 [1,2,3,4,5], k=3：
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
#
# 第1组（k=3个节点）:
# 找到 end 指向节点3
# start = 1, end = 3, next_group = 4
# 翻转 1->2->3 为 3->2->1
# 连接: dummy -> 3 -> 2 -> 1 -> 4 -> 5
# pre = 1, end = 1
#
# 第2组（剩余 4->5，只有2个，不够3个，不翻转）:
# end 走不到3步，结束
#
# 结果: 3 -> 2 -> 1 -> 4 -> 5
|
随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
Node.random 为 null 或指向链表中的节点。
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
# Definition for singly-linked list with random pointer.
class Node:
def __init__(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
"""
使用哈希表记录 原节点 -> 新节点 的映射关系
思路：
- 第一遍：创建所有新节点，用哈希表记录映射关系
- 第二遍：设置新节点的 next 和 random 指针
- 时间 O(n)，空间 O(n)
也可以用原地复制法，时间 O(n)，空间 O(1)：
1. 在每个原节点后插入新节点
2. 设置新节点的 random 指针（原节点的 random.next）
3. 分离两个链表
"""
if not head:
return None
# 哈希表：原节点 -> 新节点
hashmap = {}
# 第一遍：创建所有新节点
current = head
while current:
hashmap[current] = Node(current.val)
current = current.next
# 第二遍：设置新节点的指针
current = head
while current:
# 设置 next 指针
if current.next:
hashmap[current].next = hashmap[current.next]
# 设置 random 指针
if current.random:
hashmap[current].random = hashmap[current.random]
current = current.next
return hashmap[head]
# 测试用例（使用普通链表结构模拟）
class ListNode:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
def build_random_list(node_values, random_indices):
"""
构建带 random 指针的链表
node_values: 节点值列表
random_indices: 每个节点的 random 指向的索引（-1 表示 None）
"""
if not node_values:
return None, []
# 创建所有节点
nodes = [ListNode(v) for v in node_values]
head = nodes[0]
# 连接 next 指针
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i + 1]
# 设置 random 指针
for i, idx in enumerate(random_indices):
if idx >= 0 and idx < len(nodes):
nodes[i].random = nodes[idx]
return head, nodes
def get_random_indices(head):
"""获取链表中每个节点 random 指向的索引"""
if not head:
return []
# 先建立节点到索引的映射
node_to_idx = {}
current = head
idx = 0
while current:
node_to_idx[current] = idx
current = current.next
idx += 1
# 获取 random 索引
result = []
current = head
while current:
if current.random is None:
result.append(-1)
else:
result.append(node_to_idx.get(current.random, -1))
current = current.next
return result
def clone_with_check(original):
"""复制链表并验证结果"""
if not original:
return None
# 创建哈希表
hashmap = {}
current = original
while current:
hashmap[current] = ListNode(current.val)
current = current.next
# 设置指针
current = original
while current:
if current.next:
hashmap[current].next = hashmap[current.next]
if current.random:
hashmap[current].random = hashmap[current.random]
current = current.next
return hashmap[original]
# 示例1: [[7,null],[13,0],[11,4],[10,2],[1,0]]
values = [7, 13, 11, 10, 1]
randoms = [-1, 0, 4, 2, 0] # 索引 -1 表示 null
head, nodes = build_random_list(values, randoms)
cloned = clone_with_check(head)
# 验证值正确
assert cloned.val == 7
assert cloned.next.val == 13
assert cloned.next.next.val == 11
assert cloned.next.next.next.val == 10
assert cloned.next.next.next.next.val == 1
# 验证 random 正确（cloned 链表中 random 指向的应该是新链表中的节点）
assert cloned.random is None
assert cloned.next.random == cloned
assert cloned.next.next.random == cloned.next.next.next.next
assert cloned.next.next.next.random == cloned.next.next
assert cloned.next.next.next.next.random == cloned
# 示例2: [[1,1],[2,1]]
values = [1, 2]
randoms = [1, 0]
head, nodes = build_random_list(values, randoms)
cloned = clone_with_check(head)
assert cloned.val == 1
assert cloned.random == cloned.next
assert cloned.next.random == cloned
# 手动推导 [[7,null],[13,0],[11,4],[10,2],[1,0]]：
# 原链表:
# 节点0(7) -> 节点1(13) -> 节点2(11) -> 节点3(10) -> 节点4(1)
# 节点0.random = None
# 节点1.random = 节点0
# 节点2.random = 节点4
# 节点3.random = 节点2
# 节点4.random = 节点0
#
# 第一遍：创建哈希表
# hashmap = {
# 节点0: 新节点0(7),
# 节点1: 新节点1(13),
# 节点2: 新节点2(11),
# 节点3: 新节点3(10),
# 节点4: 新节点4(1)
# }
#
# 第二遍：设置指针
# 节点0.next = 节点1 -> 新节点0.next = 新节点1
# 节点0.random = None -> 新节点0.random = None
# 节点1.next = 节点2 -> 新节点1.next = 新节点2
# 节点1.random = 节点0 -> 新节点1.random = 新节点0
# ...以此类推
#
# 结果链表:
# 新节点0(7) -> 新节点1(13) -> 新节点2(11) -> 新节点3(10) -> 新节点4(1)
# 新节点0.random = None
# 新节点1.random = 新节点0
# 新节点2.random = 新节点4
# 新节点3.random = 新节点2
# 新节点4.random = 新节点0
|
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
"""
使用归并排序对链表排序（自顶向下）
思路：
- 归并排序：分而治之，将链表分成两半，分别排序，再合并
- 找中点：使用快慢指针，快指针走两步，慢指针走一步
- 递归排序左右两部分
- 合并两个有序链表
- 时间 O(n log n)，空间 O(log n)（递归栈）
进阶要求 O(1) 空间：使用自底向上的归并排序
"""
if not head or not head.next:
return head
# 1. 找到链表的中点，断开链表
slow = head
fast = head.next # important: fast 从 head.next 开始，确保中点是前半部分末尾
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None # 断开链表
# 2. 递归排序左右两部分
left = self.sortList(head)
right = self.sortList(mid)
# 3. 合并两个有序链表
return self.merge(left, right)
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
"""
合并两个有序链表
"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: [4,2,1,3] -> [1,2,3,4]
head = build_list([4, 2, 1, 3])
result = Solution().sortList(head)
assert to_list(result) == [1, 2, 3, 4]
# 示例2: [-1,5,3,4,0] -> [-1,0,3,4,5]
head = build_list([-1, 5, 3, 4, 0])
result = Solution().sortList(head)
assert to_list(result) == [-1, 0, 3, 4, 5]
# 示例3: [] -> []
head = build_list([])
result = Solution().sortList(head)
assert to_list(result) == []
# 更多测试
assert to_list(Solution().sortList(build_list([1]))) == [1]
assert to_list(Solution().sortList(build_list([2, 1]))) == [1, 2]
assert to_list(Solution().sortList(build_list([5, 4, 3, 2, 1]))) == [1, 2, 3, 4, 5]
assert to_list(Solution().sortList(build_list([3, 3, 3, 3]))) == [3, 3, 3, 3]
# 手动推导 [4,2,1,3]：
# 原始: 4 -> 2 -> 1 -> 3
#
# 分：
# 找中点: slow=2, mid=1 -> 断开
# 左: 4 -> 2
# 右: 1 -> 3
#
# 排序左 [4,2]:
# 找中点: slow=4, mid=2 -> 断开
# 左: 4
# 右: 2
# 递归排序后合并: 2 -> 4
#
# 排序右 [1,3]:
# 找中点: slow=1, mid=3 -> 断开
# 左: 1
# 右: 3
# 递归排序后合并: 1 -> 3
#
# 合并 [2,4] 和 [1,3]:
# 1<=2, 选1 -> [1]
# 2<=3, 选2 -> [1,2]
# 3<=4, 选3 -> [1,2,3]
# 选4 -> [1,2,3,4]
#
# 结果: 1 -> 2 -> 3 -> 4
|
合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
import heapq
from typing import List, Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
"""
使用最小堆合并 K 个有序链表
思路：
- 维护一个大小为 K 的最小堆
- 初始将每个链表的头节点加入堆
- 每次取出堆中最小的节点，加入结果链表
- 将取出的节点的下一个节点加入堆
- 时间 O(N log K)，N 是总节点数，K 是链表数
- 空间 O(K)
"""
# 定义最小堆的比较方式（存储 (节点值, 索引, 节点)）
heap = []
# 初始化堆：加入每个链表的头节点
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
# 将最小节点加入结果
current.next = node
current = current.next
# 将该节点的下一个节点加入堆
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
def mergeKLists_divide(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
"""
分治法合并 K 个有序链表
思路：
- 两两合并链表，减少比较次数
- 每次合并两个链表，直到只剩一个
- 时间 O(N log K)，空间 O(log K)（递归栈）
"""
if not lists:
return None
return self.divide_and_conquer(lists, 0, len(lists) - 1)
def divide_and_conquer(self, lists: List, left: int, right: int) -> ListNode:
"""
分治：合并 lists[left:right+1] 范围内的链表
"""
if left == right:
return lists[left]
mid = (left + right) // 2
left_list = self.divide_and_conquer(lists, left, mid)
right_list = self.divide_and_conquer(lists, mid + 1, right)
return self.merge_two_lists(left_list, right_list)
def merge_two_lists(self, l1: ListNode, l2: ListNode) -> ListNode:
"""合并两个有序链表"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
# 测试用例
def build_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 示例1: [[1,4,5],[1,3,4],[2,6]] -> [1,1,2,3,4,4,5,6]
lists = [build_list([1, 4, 5]), build_list([1, 3, 4]), build_list([2, 6])]
result = Solution().mergeKLists(lists)
assert to_list(result) == [1, 1, 2, 3, 4, 4, 5, 6]
# 示例2: [] -> []
lists = []
result = Solution().mergeKLists(lists)
assert to_list(result) == []
# 示例3: [[]] -> []
lists = [build_list([])]
result = Solution().mergeKLists(lists)
assert to_list(result) == []
# 更多测试
assert to_list(Solution().mergeKLists([build_list([1]), build_list([])])) == [1]
assert to_list(Solution().mergeKLists([build_list([1, 2]), build_list([3, 4])])) == [1, 2, 3, 4]
# 手动推导 [[1,4,5],[1,3,4],[2,6]]：
# 初始堆: [(1,0,节点1), (1,1,节点1), (2,2,节点1)]
#
# 第1次: 取出(1,0)，加入结果，push节点4 -> 堆: [(1,1,节点1), (2,2,节点1), (4,0,节点4)]
# 第2次: 取出(1,1)，加入结果，push节点3 -> 堆: [(2,2,节点1), (3,1,节点3), (4,0,节点4)]
# 第3次: 取出(2,2)，加入结果，push节点6 -> 堆: [(3,1,节点3), (4,0,节点4), (6,2,节点6)]
# 第4次: 取出(3,1)，加入结果，push节点4 -> 堆: [(4,0,节点4), (4,1,节点4), (6,2,节点6)]
# 第5次: 取出(4,0)，加入结果，push节点5 -> 堆: [(4,1,节点4), (5,0,节点5), (6,2,节点6)]
# 第6次: 取出(4,1)，加入结果，无下一个 -> 堆: [(5,0,节点5), (6,2,节点6)]
# 第7次: 取出(5,0)，加入结果，无下一个 -> 堆: [(6,2,节点6)]
# 第8次: 取出(6,2)，加入结果，无下一个 -> 堆: []
#
# 结果: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
|
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
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
|
from collections import OrderedDict
class LRUCache:
"""
使用 OrderedDict 实现 LRU 缓存
OrderedDict 特点：
- 保持元素插入顺序
- move_to_end() 可以将元素移到末尾（表示最近使用）
- popitem(last=True) 可以删除末尾元素（最久未使用）
时间复杂度：get O(1)，put O(1)
空间复杂度：O(capacity)
"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
"""
获取缓存值，如果存在则将其移到末尾表示最近使用
"""
if key not in self.cache:
return -1
# 移到末尾，表示最近使用
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
"""
放入缓存，如果已存在则更新值并移到末尾
如果不存在且缓存满，先删除最久未使用的（头部）
"""
if key in self.cache:
# 已存在，更新值并移到末尾
self.cache.move_to_end(key)
self.cache[key] = value
else:
# 不存在，检查容量
if len(self.cache) >= self.capacity:
# 删除最久未使用的（头部）
self.cache.popitem(last=False)
# 添加新元素（自动在末尾）
self.cache[key] = value
# 测试用例
cache = LRUCache(2)
cache.put(1, 1) # 缓存: {1=1}
cache.put(2, 2) # 缓存: {1=1, 2=2}
assert cache.get(1) == 1 # 返回 1，缓存: {2=2, 1=1}（1最近使用）
cache.put(3, 3) # 删除最久未使用的 2，缓存: {1=1, 3=3}
assert cache.get(2) == -1 # 返回 -1（已删除）
cache.put(4, 4) # 删除最久未使用的 1，缓存: {3=3, 4=4}
assert cache.get(1) == -1 # 返回 -1（已删除）
assert cache.get(3) == 3 # 返回 3
assert cache.get(4) == 4 # 返回 4
# 手动推导操作序列：
# ["LRUCache","put","put","get","put","get","put","get","get","get"]
# [[2], [1,1],[2,2], [1], [3,3], [2], [4,4], [1], [3], [4]]
#
# 初始: capacity=2, cache={}
#
# put(1,1): cache={1:1}
# put(2,2): cache={1:1, 2:2}
# get(1): 返回1，cache={2:2, 1:1}（1移到末尾）
# put(3,3): cache满了，删除最久未使用的2 -> cache={1:1}，然后添加3 -> cache={1:1, 3:3}
# get(2): 返回-1（2已删除）
# put(4,4): cache满了，删除最久未使用的1 -> cache={3:3}，然后添加4 -> cache={3:3, 4:4}
# get(1): 返回-1（1已删除）
# get(3): 返回3，cache={4:4, 3:3}
# get(4): 返回4，cache={3:3, 4:4}
#
# 最终: [-1,-1,3,4]（实际测试中get返回值的顺序）
|
记录生活