21. 合并两个有序链表
题目链接：21. 合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
核心思考：双指针与虚拟头节点
这是一道极其经典的链表基础操作题。因为两个链表本身已经是有序的了，所以我们可以直接使用双指针（或称归并排序的合并过程）的思路。
我们需要两个指针分别指向两个链表的当前节点，每次比较这两个节点的值：
- 取出两者中较小的那个节点。
- 将这个较小的节点接到我们正在构建的“结果链表”的末尾。
- 移动刚才被取出的节点所在链表的指针，使其指向下一个节点。
- 重复这个过程，直到其中一个链表被遍历完。
- 最后，只要把尚未遍历完的那个链表，整个儿直接拼接到结果链表的末尾即可。
虚拟头节点 (Dummy Node)：
在构建“结果链表”时，我们会面临一个边界问题：第一个放入结果链表的节点是谁？它没有前驱节点。为了避免在代码中写繁琐的 if 语句来特判头节点，链表题有一个常用的技巧——引入一个虚拟头节点 (Dummy Node)。
我们让一个永远不变的假节点作为链表的头部，所有的真实节点都挂在这个假节点之后。最后返回结果时，只需返回 Dummy.next 即可。
解题思路 (Python)
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
|
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
Head = ListNode()
curp = Head
p_1 = list1
p_2 = list2
while p_1 is not None and p_2 is not None:
if p_1.val > p_2.val:
curp.next = p_2
p_2 = p_2.next
else:
curp.next = p_1
p_1 = p_1.next
curp = curp.next
if p_1 is not None:
curp.next = p_1
if p_2 is not None:
curp.next = p_2
return Head.next
|
复杂度分析
- 时间复杂度：$O(m + n)$，其中 $m$ 和 $n$ 分别是两个链表的长度。在
while 循环中，每次我们都会把一个节点接入到合并后的链表中，因此最多执行 $m + n$ 次循环。 - 空间复杂度：$O(1)$。我们仅仅用了几个常数级别的指针 (
Head, curp, p_1, p_2) 用于追踪和连接现有的节点，并没有开辟任何与 m、n 大小相关的新空间。
![image-compressed.png]()
ACM 模式
本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。
输入格式：
1
2
| num1 num2 num3 ... numN
num1 num2 num3 ... numM
|
第一行输入第一个链表的数组表示，第二行输入第二个链表的数组表示。
完整代码：
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
| import sys
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_listnode(arr):
dummy = ListNode(0)
cur = dummy
for v in arr:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def listnode_to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
Head = ListNode()
curp = Head
p_1 = list1
p_2 = list2
while p_1 is not None and p_2 is not None:
if p_1.val > p_2.val:
curp.next = p_2
p_2 = p_2.next
else:
curp.next = p_1
p_1 = p_1.next
curp = curp.next
if p_1 is not None:
curp.next = p_1
if p_2 is not None:
curp.next = p_2
return Head.next
def main():
lines = sys.stdin.read().strip().split()
list1_arr = list(map(int, lines[0].split())) if lines[0] else []
list2_arr = list(map(int, lines[1].split())) if len(lines) > 1 and lines[1] else []
list1 = build_listnode(list1_arr)
list2 = build_listnode(list2_arr)
sol = Solution()
result = sol.mergeTwoLists(list1, list2)
print(listnode_to_list(result))
if __name__ == "__main__":
main()
|
