题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）

题解

这道题速度快和内存少，基本上就是迭代更新节点的方法，这样用去的时间是O(min(len(l1), len(l2)))，使用的空间就只有一两个指针，也就是S(1)。如果使用一个新的链表去承接这些节点，那么空间复杂度就有O(n)了。

这个题解中最精髓的地方在循环判断的l1 && l2和之后循环结束的o->next = l1?l1:l2;。

因为输入的链表是有序的，所以在将其中一个链表扫描完成之后，只需要将另一条链表直接连接在末尾就可以了。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *o, begin(0);
        o = &begin;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                o->next = l1;
                l1 = l1->next;
            } else {
                o->next = l2;
                l2 = l2->next;
            }
            o = o->next;
        }
        o->next = l1?l1:l2;
        return begin.next;
    }
};

结果

执行用时 : 12 ms, 在所有 C++ 提交中击败了86.67%的用户
内存消耗 : 8.7 MB, 在所有 C++ 提交中击败了95.20%的用户