0021.Merge-Two-Sorted-Lists

合并两个有序链表

1. 题目

1.1. 描述

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

1.2. 示例

示例 1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2

输入：l1 = [], l2 = []
输出：[]

示例 3

输入：l1 = [], l2 = [0]
输出：[0]

1.3. 提示

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

2. 思路

2.1. 迭代法

类似于归并排序中插入有序数组

• 新建链表，采用尾插法
• 比较两个链表的元素值，较小的元素值结点链接到新链表中
• 最后未遍历完的链表链接到新链表中
• 时间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度
• 空间复杂度为O(1)

2.2. 递归法

• 比较两个链表当前结点值，保存较小值结点，递归比较该链表下一个结点和另一个链表当前结点
• 时间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度
• 空间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度

3. 代码

3.1. C++

3.1.1. 迭代法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 新链表
        ListNode *ans = new ListNode(-1);
        ListNode *p = ans;
        // 循环遍历
        while(list1!=NULL&&list2!=NULL){
            int a = list1->val;
            int b = list2->val;
            // 新链表结点指向较小值的结点
            if(a<=b){
                p->next = list1;
                p=list1;

                list1=list1->next;
            }else{
                p->next = list2;
                p=list2;

                list2=list2->next;
            }
        }
        // 剩余结点直接链入新链表
        while(list1!=NULL){
            p->next = list1;
            p=list1;

            list1=list1->next;
        }
        while(list2!=NULL){
            p->next = list2;
            p=list2;

            list2=list2->next;
        }
        return ans->next;
    }
};

3.1.2. 递归法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL){ return list2; }
        if(list2==NULL){ return list1; }
        if(list1->val<=list2->val){ 
            // 较小的结点与剩余结点合并
            list1->next= mergeTwoLists(list1->next,list2);
            return list1; 
        }else{
            list2->next= mergeTwoLists(list1,list2->next);
            return list2; 
        }
    }
};

3.2. Java

3.2.1. 迭代法

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode(-1);
        ListNode p=ans;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                p.next=list1;
                p=list1;
                list1=list1.next;
            }else{
                p.next=list2;
                p=list2;
                list2=list2.next;
            }
        }
        while(list1!=null){
            p.next=list1;
            p=list1;
            list1=list1.next;
        }
        while(list2!=null){
            p.next=list2;
            p=list2;
            list2=list2.next;
        }
        return ans.next;
    }

}

3.2.2. 递归法

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){ return list2; }
        if(list2==null){ return list1; }
        if(list1.val<=list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}