【力扣刷题练习】21. 合并两个有序链表

题目描述：

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

题目解答：

1. 递归解法

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

2. 创建新链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1 || !list2)
            return list1 == nullptr ? list2 : list1;
        vector<int> demolist;
        while (list1 != nullptr) {
            demolist.push_back(list1->val);
            list1 = list1->next;
        }
        while (list2 != nullptr) {
            demolist.push_back(list2->val);
            list2 = list2->next;
        }
        sort(demolist.begin(), demolist.end());
        ListNode *p = new ListNode(demolist[0]), *head = p;
        int len = demolist.size();
        for (int i = 1; i < len; i++) {
            ListNode* t = new ListNode(demolist[i]);
            p->next = t;
            p = p->next;
        }
        return head;      
    }
};

题目思路：

1. 递归解法思路：

一种经典的递归解法，用于合并两个有序链表

首先检查list1 和 list2 是否有一个为空指针。如果其中一个为空，就返回另一个链表，因为其中一个链表为空意味着不需要合并，直接返回另一个链表即可。

如果两个链表都不为空，就比较它们当前节点的值。如果 list1 的当前节点值小于 list2 的当前节点值，那么将 list1 的下一个节点与排序好的 list2 合并（递归调用 mergeTwoLists 函数），然后返回 list1，表示当前最小值的节点是 list1 的当前节点。

反之，如果 list2 的当前节点值小于或等于 list1 的当前节点值，就将 list2 的下一个节点与排序好的 list1 合并（同样是递归调用 mergeTwoLists 函数），然后返回 list2，表示当前最小值的节点是 list2 的当前节点。

这个递归过程会一直持续，直到其中一个链表为空，然后将另一个非空链表直接连接到已排序的链表尾部。这样，就能够正确合并两个已排序链表，并返回合并后的链表头节点。

2. 新链表思路：

如果其中一个链表为空，直接返回另一个非空链表。
空整数向量 demolist 用于暂存链表节点的值，用两个 while 循环将链表 list1 和 list2 中的节点值依次添加到 demolist 向量中。
接下来用 std::sort 对 demolist 中的所有值进行排序，确保这些值按照升序排列。

做完上述准备工作后，创建一个新的链表，根据排序后的 demolist 向量中的值构建新的链表，然后遍历 demolist 中的值，逐个创建新的节点，然后连接到链表中，最后返回新链表的头节点 head。