合并有序列链表

Leetcode算法练习第二十一题：合并有序链表

<!- more -->

问题描述

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

示例：

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

解法一

同步循环遍历两个链表，用一个新表存储较小值，然后将较小值对应的链表指针后移一位；重复该过程。最后判断一下两个链表中的剩余链表，将其接入新表。

复杂度

由于需要遍历链表，故时间复杂度为O(n)，而储存新表需要空间O(n)。

Python

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None and l2 is None:
            return None
        if l1 is None and l2 is not None:
            return l2
        if l1 is not None and l2 is None:
            return l1

        p=h=None
        if l1.val<l2.val:
            p=h=ListNode(l1.val)
            l1=l1.next
        else:
            p=h=ListNode(l2.val)
            l2=l2.next
        while l1 and l2:
            if l1.val<l2.val:
                p.next=ListNode(l1.val)
                p=p.next
                l1=l1.next
            else:
                p.next=ListNode(l2.val)
                p=p.next
                l2=l2.next
        while l1:
            p.next=ListNode(l1.val)
            p=p.next
            l1=l1.next
        while l2:
            p.next=ListNode(l2.val)
            p=p.next
            l2=l2.next
        return h

解法二

考虑两个链表，当我们分别对比他们的第一个元素挑出较小值后，问题变为对比较小值后面的元素跟另一链表的当前值，然后挑出较小值，同理一直进行下去.....，故我们发现这是一个动态规划的问题，我们可以用递归的方式来实现。

复杂度

递归调用实际上针对每一个问题的子问题的子问题....，这样，倒过来看就是从1到2到3到....，一直到原问题的n，这样，时间复杂度就是$$O(n)$$ ，空间上递归需使用的递归调用栈占用$$O(n)​$$ 的空间。

C++

static const auto io_sync_off=[](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)return NULL;
        if(l1==NULL && l2!=NULL)return l2;
        if(l1!=NULL && l2==NULL)return l1;
        
        if(l1->val<l2->val){
            l1->next=this->mergeTwoLists(l1->next,l2);
            return l1;
        }  
        else{
            l2->next=this->mergeTwoLists(l1,l2->next);
            return l2;
        }  
    }
};

Python

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None and l2 is None:
            return None
        if l1 is None and l2 is not None:
            return l2
        if l1 is not None and l2 is None:
            return l1
        
        if l1.val > l2.val:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
        else:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1