21.合并两个有序链表

题目链接

https://leetcode.cn/problems/merge-two-sorted-lists

解题思路

双指针

根据题目描述, 链表l1和l2是非减的, 所以想到可以用双指针l1和l2遍历两个链表. 根据l1.val和l2.val的大小关系确定添加节点的顺序, 两指针交替前进, 直到其中一个链表遍历完成, 拼接上另一个链表.

在这里, 我们需要引入一个"哨兵节点". 这个节点代表的是合并后链表的初始节点. 这样就避免了开始的时候要从l1或者l2里面选出一个最小的当头节点. 虽然牺牲了一个单位的空间, 但是在观感和简洁程度上获得很大提升.

算法可以描述为:

1. 添加"哨兵节点", 并初始化一个指针cur永远指向合并数组的最后一个节点
2. 循环合并♻️: 当l1或者l2为空的时候弹出
   • 当l1.val小于等于l2.val的时候, cur的后继节点为l1, l1向后移动一个单位
   • 当l1.val大于l2.val的时候, cur的后继节点为l2, l2向后移动一个单位
   • cur向后移动一个单位
3. 合并剩余尾部:
   • 当l1不为空的时候, 将l1的尾部拼接到合并数组尾部
   • 当l2不为空的时候, 将l2的尾部拼接到合并数组尾部
4. 返回值: 应该返回的是"哨兵节点"的下一个节点

# ⌚ 45ms 📀 16.3MB
# 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: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 边缘案例
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        # 生成哨兵节点
        head = ListNode(0)
        # 将当前节点指向哨兵节点
        cur = head
        # 循环合并
        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        # 合并剩余尾部
        if list1 != None:
            cur.next = list1
        if list2 != None:
            cur.next = list2
        # 返回值
        return head.next

递归

信息

参考题解链接: https://leetcode.cn/problems/merge-two-sorted-lists/solutions/103891/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/

• 归: 当一个链表中的节点全部处理完毕的时候, 即l1或l2为空的时候, 直接返回另外一个链表的剩余部分, 这是"归"的开始, 返回的节点将会称为上一个小的节点的next指向的节点
• 递: "递"发生在比较链表的两个节点的值之后, 调用函数本身, 较小的节点的next指针将会指向"归"返回的结果.

# ⌚ 36ms 📀 16.50MB
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2