题目的主要信息：

• 两个递增的链表，单个链表的长度为$nn$
• 合并这两个链表并使新链表中的节点仍然是递增排序的
• 要求：空间复杂度 $O(1)O(1)$，时间复杂度 $O(n)O(n)$

方法一：递归（能过，空间不符合要求）

具体做法：

连接链表可以递归解决。我们每次比较两个链表当前结点的值，然后取较小值的链表指针往后，另一个不变送入递归中，添加后续的结点，而递归回来的结果我们要加在较小值的结点后面，相当于不断在较小值后面添加结点。而递归的终止是两个链表为空。

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == NULL) //一个已经为空了，返回另一个
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        if(pHead1->val <= pHead2->val){ //先用较小的值的结点
            pHead1->next = Merge(pHead1->next, pHead2); //递归往下
            return pHead1; 
        }else{
            pHead2->next = Merge(pHead1, pHead2->next); //递归往下
            return pHead2;
        }
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏相当于遍历两个链表每个结点一次
• 空间复杂度：$O(n)O(n)$，递归栈长度最大为$nn$

方法二：迭代

具体做法：

我们可以新建一个空的表头后面连接两个链表排序后的结点。首先遍历两个链表都不为的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。遍历到最后肯定有一个链表还有剩余的结点，它们的值将大于前面所有的，直接连在新的链表后面即可。

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == NULL) //一个已经为空了，直接返回另一个
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        ListNode* head = new ListNode(0); //加一个表头
        ListNode* cur = head;
        while(pHead1 && pHead2){ //两个链表都要不为空
            if(pHead1->val <= pHead2->val){ //取较小值的结点
                cur->next = pHead1;
                pHead1 = pHead1->next; //只移动取值的指针
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next; //只移动取值的指针
            }
            cur = cur->next; //指针后移
        }
        if(pHead1) //哪个链表还有剩，直接连在后面
            cur->next = pHead1;
        else
            cur->next = pHead2;
        return head->next; //返回值去掉表头
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏情况遍历$2\ast n2*n$个结点
• 空间复杂度：$O(1)O(1)$，无额外空间使用，新建的链表属于返回必要空间