LeetCode Merge Two Sorted Lists（合併兩個有序鏈表）

一、題目描述

將兩個升序鏈表合併為一個升序鏈表，返回新頭節點。要求原地操作（不新建節點），直接串聯原節點。

範例： 1→2→4, 3 → 1→2→3→4

二、解題思路：虛擬頭節點 + 雙指針

創建 dummy 節點，tail 指向結果鏈表尾部。同時遍歷 l1、l2，比較值，將較小節點接到 tail 後，移動對應指針。一條鏈表耗盡後，直接連接另一條剩餘部分。

三、代碼實現（Python）

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        tail = dummy
        while l1 and l2:
            if l1.val > l2.val:
                tail.next = l2
                l2 = l2.next
            else:
                tail.next = l1
                l1 = l1.next
            tail = tail.next
        tail.next = l1 if l1 else l2
        return dummy.next

# 測試
if __name__ == "__main__":
    assert Solution().mergeTwoLists(ListNode(1), ListNode(2)).val == 1

四、複雜度分析

• 時間：O(N+M)
• 空間：O(1)

虛擬頭節點統一了頭節點處理邏輯，是鏈表題常用技巧。