🚗题目描述

将两个升序链表合并为一个新的

升序

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

示例 1：

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

示例 2：

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

示例 3：

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

🥖 解法一：朴素迭代

思路：

先判断

链表为空

的情况，若链表一为空则返回链表二的头结点，反之则返回链表一的头结点；设置头结点

head

和尾结点

tail

置空，先判断list1和list2头结点大小

head=tail=较小的头结点

，再比较list1和list2的值进行迭代，较小的值尾插到tail的后面，即可实现有序合并两个链表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr){return list2;}
        if(list2==nullptr){return list1;}
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        while(list1  && list2){
            if(list1->val < list2->val){
                if(head == nullptr){
                    head = tail = list1;
                }else{
                    tail->next = list1;
                    tail = list1;
                }
                list1 = list1->next;
            }else{
                if(head == nullptr){
                    head = tail = list2;
                }else{
                    tail->next = list2;
                    tail = list2;
                }
                list2 = list2->next;
            }
        }
        if(list1){
            tail->next = list1;
        }
        if(list2){
            tail->next = list2;
        }
        return head;
    }
};

🥖 解法二：有哨兵的迭代

思路：设置虚的头结点即哨兵，就省去了上面朴素迭代设置头结点为链表小的那个的步骤，直接进行尾插，返回的时候记得返回dummyhead的下一个为头结点，清除dummyhead。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr){return list2;}
        if(list2==nullptr){return list1;}
        ListNode* dummyhead = new ListNode(0);
        ListNode* tail = dummyhead;
    
        while(list1  && list2){
            if(list1->val < list2->val){
                    tail->next = list1;
                    tail = list1;
                    list1 = list1->next;
            }else{
                    tail->next = list2;
                    tail = list2;
                    list2 = list2->next;
            }
        }
        if(list1){
            tail->next = list1;
        }
        if(list2){
            tail->next = list2;
        }
        ListNode* ret = dummyhead->next;
        delete dummyhead;
        return ret;
    }
};

🥖 解法三：有点难理解的递归

注意链表自带递归属性，在使用递归之前还是回想想一下递归的用法

递归方法总结：

1.明确递归方法要实现什么功能？

判断 list1 和 list2 头结点哪个更小，然后较小结点的

next

指针指向

其余结点的合并结果。（调用递归）

2.明确递归开始结束的条件？–当 list1 和 list2 都为空时表明递归完成

3.返回给上一级什么值？–返回处理后的头结点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr){ return list2;}
        if(list2==nullptr){ return list1;}
        if(list1->val<list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list1,list2->next); 
            return list2;
        }
    }
};

——–以上为四种解题思路，仅供参考~