合并两个有序链表

🟢 Easy · 🏷️ 链表 · LeetCode#21

📖 题目

将两个升序链表合并成一个升序链表。

输入	输出
list1=1→2→4, list2=1→3→4	1→1→2→3→4→4

💡 思路

合并后仍要保持有序，所以要用尾插法：每次比较两个链表当前节点，把较小的那个接到结果链表的尾部，对应链表往后移一位。

用一个 dummy 节点当锚点简化头部处理（不用单独判断"第一个节点特殊在哪"），cur 指针负责在尾部接新节点，一直往后挪。哪个链表先走完了，剩下那条直接整段接上去，不用再逐个比较。

💻 代码

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2   # 剩余部分直接接上
        return dummy.next

时间复杂度 O(m + n)，两个链表各遍历一次；空间复杂度 O(1)，复用的是原节点，没有新建节点。

cur.next = cur 和 cur = cur.next 别写反——前者会让节点自己指向自己，形成环，导致死循环。