如何合并两个有序链表？

如何 合并两个有序链表 ？

假设链表 a 和 b 的长度都是 n，要在 O(n) 的时间代价以及 O(1) 的空间代价完成合并。我们的宗旨是 [原地调整链表元素的 next 指针完成合并]。

• 首先需要一个变量 head 来保存合并之后链表的头部，可以将 head 设置为一个虚拟的头(方便代码的书写)，在整个链表合并完之后，返回它的下一位置。
• 需要一个一直变化的指针 tail 来记录下一插入位置的前一位置，以及两个指针 aPtr 和 bPtr 记录 a 和 b 未合并部分的第一位。
• 当 aPtr 和 bPtr 都不为空时，取 val 更小的合并；如果 aPtr 为空，把整个 bPtr 以及之后的元素全部合并；aPtr 同理。
• 在合并的时候先要调整 tail 的 next 属性，再后移 tail 和 Ptr 。

/*
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
ListNode* merge_two_lists(ListNode* a, ListNode* b) {
    if (!a || !b) {
        return a ? a : b;
    } 
    ListNode head;
    ListNode* tail = &head;
    ListNode* aPtr = a;
    ListNode* bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr;
            aPtr = aPtr->next;
        }
        else {
            tail->next = bPtr;
            bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}