Leetcode题解 - 21. 合并两个有序链表

🔗题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

🔗示例

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

🔗解题思路

最简单的方法是，遍历第一个链表，将每个元素插入到第二个链表对应位置，时间复杂度为$O(m×n)$，空间复杂度为$O(1)$。

代码：

# 链表节点
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # 边界情况，某一个链表为空，则直接返回另一个链表
    if l1 is None:
        return l2
    elif l2 is None:
        return l1
    # 创建头节点，方便返回
    phead = ListNode(0)
    phead.next = l2
    # 遍历l1节点，与l2的每个节点相比较
    while l1 is not None:
        # 每次遍历完l2后，使l2归位
        l2 = phead.next
        
        while l2 is not None:
            # 如果l1节点小于等于l2，则直接插到l2前面
            if l1.val <= l2.val:
                # insert head
                tmp = l1.next
                l1.next = phead.next
                phead.next = l1
                l1 = tmp
                break
            # 如果l1节点大于l2，则插在后面，但要注意防止越界
            elif l2.next is not None and l2.val < l1.val <= l2.next.val or l2.next is None and l2.val < l1.val:
                # insert rear
                tmp = l1.next
                l1.next = l2.next
                l2.next = l1
                l1 = tmp
                break
            else:
                l2 = l2.next

    return phead.next

再看看官方题解，一对比，差距太大，看了好一会才看懂。

时间复杂度为$O(m+n)$。

代码：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 声明头节点，方便返回
        phead = ListNode(-1)
        # 游标节点，用来连接比较后的最小值
        p = phead
        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 is not None else l2
        return phead.next

测试用例：

if __name__ == "__main__":
    s = Solution()
    l1 = ListNode(1)
    t1 = l1
    l2 = ListNode(2)
    t2 = l2
    for i in range(2):
        t1.next = ListNode(t1.val + 2)
        t2.next = ListNode(t2.val + 2)
        t1 = t1.next
        t2 = t2.next
    t = s.mergeTwoLists(l1, l2)
    while t is not None:
        print(t.val)
        t = t.next