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

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

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // 如果任意一个链表为空，直接返回另一个链表
        if (pHead1 == nullptr) return pHead2;
        if (pHead2 == nullptr) return pHead1;

        // 确保 pHead1 指向较小的头节点
        if (pHead1->val > pHead2->val) {
            std::swap(pHead1, pHead2);
        }

        ListNode* p1 = pHead1;  // 遍历 pHead1
        ListNode* p2 = pHead2;  // 遍历 pHead2
        ListNode* pre1 = nullptr;  // 用于记录 p1 的前一个节点

        // 遍历两个链表进行合并
        while (p2) {
            // 找到合适位置插入 p2
            while (p1 && p1->val <= p2->val) {
                pre1 = p1;  // 记录 p1 的前驱节点
                p1 = p1->next;  // 移动 p1 指针
            }

            // 要判断p1是不是走到最后了，是的话直接将p2剩下的接上!!!
            if (p1==nullptr) {
               pre1->next=p2;
                return pHead1;
            }

            // 插入 p2 到 p1 前面
            pre1->next = p2;  // pre1 连接 p2
            ListNode* next_p2 = p2->next;  // 保存 p2 的下一个节点
            p2->next = p1;  // p2 连接到 p1
        //插入p2后，应该把pre1更新到p2上！！！
            pre1=p2;
            // 移动 p2 指针
            p2 = next_p2;

        }

        return pHead1;
    }
};