LeetCode 筆記：合併兩個有序鏈表

題目：合併兩個升序鏈表為一個新升序鏈表，要求拼接原節點（不創建新節點）。

分析

雙指針 p1, p2 遍歷兩表。引入虛擬頭節點 Head，Pre 指向結果表尾。每輪比較 p1->val 和 p2->val，較小者接在 Pre 後，推進對應指針與 Pre。一表遍歷完後，直接將另表剩餘部分接上。邊界：任一表為空直接返回另一表。

C++ 實現

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* p1, ListNode* p2) {
        if (!p1) return p2;
        if (!p2) return p1;
        ListNode Head(0);
        ListNode* Pre = &Head;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                Pre->next = p1;
                p1 = p1->next;
            } else {
                Pre->next = p2;
                p2 = p2->next;
            }
            Pre = Pre->next;
        }
        Pre->next = p1 ? p1 : p2;
        return Head.next;
    }
};

小結

基礎鏈表操作考點：虛擬頭節點簡化邊界，拼接而非複製節點，處理好剩餘部分接管。簡單題最見功力，邊界條件必須全覆蓋。