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

C++ ①正常合并-用带哨兵节点的链表 ②递归

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        ListNode* L = new ListNode(-1), *ph = L;
        ListNode* p1 = pHead1, *p2 = pHead2;
        while (p1) {
            // cout << p1->val << ' ' << p2->val << endl;
            if (p2 && p1->val <= p2->val) {
                ph->next = p1;
                ph = ph->next;
                p1 = p1->next;
            }
            else if (p2) {
                // cout << p1->val << endl;
                while (p2 && p2->val < p1->val) {
                    ph->next = p2;
                    ph = ph->next;
                    p2 = p2->next;
                }
            }                
            else break;
            // cout << ph->val << endl;            
        }

        if (p1) ph->next = p1;
        else if (p2) ph->next = p2;
        return L->next;
    }
};

递归

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        if (pHead1->val <= pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};