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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
*/
//法思路
//使用双指针法遍历两个链表，比较节点值大小，将较小的节点链接到新链表中。
//关键点：
//使用虚拟头节点简化边界处理
//双指针分别遍历两个链表
//时间复杂度 O(n)，空间复杂度 O(1)
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;

        // 双指针遍历两个链表
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;

        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val) {
                cur->next = p1;
                p1 = p1->next;
            } else {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }

        // 处理剩余节点
        if (p1 != nullptr) {
            cur->next = p1;
        }
        if (p2 != nullptr) {
            cur->next = p2;
        }

        ListNode* result = dummy->next;
        delete dummy;  // 释放虚拟头节点
        return result;
    }
};