题目描述

分析

这道题实际的解法是要通过递归来写，由于链表的特性：链表的任何一个子表都是链表。所以很多链表的算法用递归来写会非常简便。这里先尝试着写一下非递归的算法，再写一遍递归的算法。
非递归：

class Solution {
public:
    // void Insert(ListNode* node1, ListNode* node2){
    //     //将node2的元素值插入到node1的后面
    //     ListNode* newNode = new ListNode(node2->val, node1-> next);
    //     node1 -> next = newNode;
    //     return ;
    // }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr){
            return list2;
        }
        if(list2 == nullptr){
            return list1;
        }
        ListNode* Dummy1 = new ListNode();
        ListNode* Dummy2 = new ListNode();
        Dummy1 -> next = list1;
        Dummy2 -> next = list2;
        ListNode* cur1 = Dummy1;
        ListNode* cur2 = Dummy2;

        int num;
        //把cur2的结点依次加入到cur1中
        while(cur2 -> next != nullptr){
            num = cur2 -> next -> val;
            while(cur1 -> next != nullptr && num >= cur1 -> next -> val){
                cur1 = cur1 -> next;
            }
            ListNode* newNode = new ListNode(num, cur1-> next);
            cur1-> next = newNode;
            cur1 = newNode;
            cur2 = cur2 -> next;
        }
        // //处理list2的剩余部分
        // if(cur2 )
        return Dummy1 -> next;
    }
};

如上所示，按常规的思路，注意还是尽量用附加头节点，否则指针移动到链表结尾时会很不好处理，就算能处理好代码也会很臃肿。
在写关于链表的算法时都要想一想能不能用递归算法秒杀。
下面展示一下官方题解的递归算法：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
	//开头两个条件分支是处理有空链表时的特殊情况
	//不仅如此，这个情况也是递归到最底下的最终原子情况，
	//到这里后递归开始回溯
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
	//后面两个分支，把较小的一个链表结点选中为已处理好的部分，
	//然后利用递归把剩下的部分再合并，接到已处理部分的后面
	//非常巧妙
    }
};