21. 合并两个有序链表(Easy)
# 题目描述
# 样例
Input:1->2->4, 1->3->4
Output:1->1->2->3->4->4
1
2
2
# 解题思路
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
伪节点
- 创建新的伪节点作为合并的头,按照大小加入节点后。
- 最后有剩余的节点,一口气加入。
递归
- 使用较小的链表的
头结点
作为头
- 因为如果有一列是空的,那么应该范围另外一列。对 终止条件 的设置很巧妙
# Python示例
伪节点【推荐】
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummpyHead = ListNode(None)
p = dummpyHead
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 if l1 else l2
return dummpyHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
递归
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54