leetcode21—合并两个有序链表
关键词:链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists
1.迭代
遍历两个链表,依次比较结点值,将较小的结点加入链表。
# 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, l1: ListNode, l2: ListNode) -> ListNode:
root = ListNode(None)
node1 = root
# while l1 is not None and l2 is not None:
# 两链表进行比较的部分,直到一方为空
while l1 and l2:
if l1.val < l2.val:
node1.next = l1
node1 = node1.next
l1 = l1.next
else:
node1.next = l2
node1 = node1.next
l2 = l2.next
# 将剩余非空的一方直接相连
node1.next = l1 if l1 is not None else l2
# while l1 is not None:
# node1.next = l1
# l1 = l1.next
# node1 = node1.next
# while l2 is not None:
# node1.next = l2
# node1 = node1.next
# l2 = l2.next
return root.next
两链表依次取结点进行比较,直到一方为空,跳出循环,将剩余的非空的一方直接与新链表进行相连。
不需要再一个一个连接。
复杂度分析:
- 时间复杂度:
O
(
m
+
n
)
O(m+n)
m
m
l1
结点数,n
n
l2
结点数。依次遍历列表。 - 空间复杂度:
O
(
1
)
O(1)
2.递归
如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
算法:
先有核心的递归处理部分:
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
每次选择较小的值x1并返回x1,将剩余列表中较小的下一个值x2与x1相连。
这里返回的值就表示加入新链表的值。
然后处理当一方为空的情况:
if l1 is None:
return l2
elif l2 is None:
return l1
就将另一方链表剩余的第一个结点返回, 连接到新链表中,因为另一方已经处于有序连接状态,所以不需要再进行额外操作。
从整体看,这种返回值的结构在第一次就返回了较小的一个结点,即新链表的头结点。不需要额外处理。
复杂度分析:
- 时间复杂度:
O
(
m
+
n
)
O(m+n)
m
m
l1
结点数,n
n
l2
结点数。依次遍历列表。 - 空间复杂度:
O
(
m
+
n
)
O(m+n)
总结
递归方法很巧妙,使用起来还是很复杂的。
处理时要注意一方为空时,直接连接另一方一次即可,不用对另一方的剩余结点一个一个连接(本就处于有序连接状态)。