合并两个有序链表21

地址：https://leetcode.cn/problems/merge-two-sorted-lists/

题干

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

思路

这道题本身是链表里面比较简单的题。

List1和list2的值相互比较，相等默认选list1的节点接入临时链表，如果1更小，接入1，如果2更小，接入2.

这里最难理解的应该是链表的指针，首先每次比对完之后应该把ListX更新到下一个节点，然后cur往后移。

说的再清楚一些：

第一轮比较：两个头节点都是1，假设 <= 时选 list1，那么把 list1 的 1 接到 cur 后面，然后 list1 移到下一个（即2），cur 也移到那个1节点上。

第二轮：比较 list1 的 2 和 list2 的 1，选 list2 的 1，接到 cur 后面...

list1 的头节点 1 被选中，接到 cur->next。
cur 指向 dummy，所以 dummy->next = list1 节点。
然后 list1 指针后移到 [2]。
cur 移动到新节点 [1]（即 cur = cur->next）。

状态：
dummy: [0] -> [1] -> nullptr
list1: [2] -> [4] -> nullptr
list2: [1] -> [3] -> [4] -> nullptr
cur 指向 [1]

cur 指向 [1]，将 cur->next 指向 list2 的 [1] 节点。
list2 后移到 [3]。
cur 移动到新节点 [1](第二个1)。

状态：
dummy: [0] -> [1] -> [1] -> nullptr
list1: [2] -> [4] -> nullptr
list2: [3] -> [4] -> nullptr
cur 指向第二个 [1]

temp 节点（值为0）的 next 指向整个合并链表的头节点（即第一个被接上的节点）。所以返回的是temp的next。

提示

不要搞混了，temp全程只是个占位符，它根本没有动过，所以它一定会指向合并链表的头节点。

cur 指针经过多次移动，此时指向合并后链表的最后一个节点。

题解

/**
 * 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* temp = new ListNode(0);
        ListNode* cur  = temp;
        while(list1!=nullptr&&list2!=nullptr){
            if(list1->val<=list2->val){
                cur->next = list1;
                list1 = list1->next;
            }else{
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        if(list1!=nullptr){
            cur->next = list1;
        }else{
            cur->next = list2;
        }
        ListNode* res = temp->next;
        delete temp;
        return res;
    }
};