题解 | 合并两个排序的链表

/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // 1. 创建虚拟头节点（哨兵节点），简化头节点处理
        ListNode* dummy = new ListNode(0);
        // 2. 定义游标指针，用于拼接新链表
        ListNode* cur = dummy;
        
        // 3. 同时遍历两个链表，直到其中一个遍历完
        while (pHead1 != nullptr && pHead2 != nullptr) {
            // 4. 比较当前节点值，将较小的节点接入新链表
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next; // 移动p1指针
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next; // 移动p2指针
            }
            cur = cur->next; // 移动游标指针
        }
        
        // 5. 处理剩余未遍历完的链表（直接拼接即可）
        if (pHead1 != nullptr) {
            cur->next = pHead1;
        }
        if (pHead2 != nullptr) {
            cur->next = pHead2;
        }
        
        // 6. 返回合并后链表的真实头节点（跳过虚拟头节点）
        ListNode* result = dummy->next;
        delete dummy; // 释放虚拟头节点内存，避免内存泄漏
        return result;
    }
};