LeetCode 21、合并两个有序链表

21、合并两个有序链表

1）题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

2）分析

递归： 两个链表头部结点值较小的一个与剩下元素merge操作的结果合并，直到其中一个链表为空，递归结束。时间复杂度O(m+n)，空间复杂度O(m+n)。

迭代： 递归的迭代写法。设定两个新的指针，preHead和preNext，分别用来指向头结点和要合并的结点。同时遍历两个链表，将他们头结点较小合并到preHead的尾部，直到其中一个链表为空，再将另一个非空链表剩下的部分合并到preHead尾部。

3）C++代码

递归

/** * Definition for singly-linked list. * 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) {} * }; */
class Solution {
    
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
        if(!list1)
            return list2;
        else if(!list2)
            return list1;
        else if(list1->val<list2->val){
    
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        else{
    
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

迭代

/** * Definition for singly-linked list. * 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) {} * }; */
class Solution {
    
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
        ListNode* preHead=new ListNode();
        ListNode* preNext=preHead;

        while(list1&&list2){
    
            if(list1->val<list2->val){
    
                preNext->next=list1;
                list1=list1->next;
            }
            else{
    
                preNext->next=list2;
                list2=list2->next;
            }
            preNext=preNext->next;
        }
        preNext->next=!list1?list2:list1;
        return preHead->next;
    }
};