21.合并两个有序链表.md

/**
 * 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) {}
 * };
 */

// 最佳解法：2个升序链表，cur逐个遍历从小到大依次链接
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy_node = new ListNode();
        ListNode* cur = dummy_node;
        // 虚拟头节点，从第0个开始选择链接l1、l2的第一个最小node
        // 一旦哪个链表为null，即可终止，把另外的接在后面即可
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        // 接上非空的，非空的此时一定是升序，且比已链接好的node都更大。
        cur->next = list1 ? list1 : list2;
        return dummy_node->next;
    }
};

 // 复习
 //  这个是自己想的解法，将2个链表先用2个for遍历，用一个vec装他们的值，然后sort排序，然后新建链表，
 // 按vec中排好序的值。
 
 // 但这样的解法不好：用了sort排序，而且new了新的node，不是拼接，还用了vec。

/* class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        vector<int> all_node;
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        while (cur1) {
            all_node.push_back(cur1->val);
            cur1 = cur1->next;
        }
        while (cur2) {
            all_node.push_back(cur2->val);
            cur2 = cur2->next;
        }
        sort(all_node.begin(), all_node.end());
        ListNode* dummy_node = new ListNode(0);
        ListNode* cur = dummy_node;
        for (auto val : all_node) {
            ListNode* tmp = new ListNode(val);
            cur->next = tmp;
            cur = cur->next;
        }
        return dummy_node->next;
    }
}; */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 如果递归过程中，list1已经遍历完了，那么就可以终止递归返回了，只需要把list2剩下的
        // 这些剩下的一定逗比list1值大）当做尾巴，返回即可。
        if (list1 == nullptr)
            return list2;

        // 同上。
        if (list2 == nullptr)
            return list1;

        // 如果list1值更小，那就让list1来连接后面（即list1放在更左），给list1->next赋值。
        // 这个递归的过程，其实主要就是两步，递归不断进入+递归不断返回。
        // 每次进入下一层递归，都有参数上的移动，即ListNode* list1 = list1->next这种。
        // 所以每层递归的list1、list2指向的位置是不同的，list1、list2随着递归深入不断前进移动，
        // 但在递归返回时，也不断又回退最终靠回head node。
        // 这个拼接的过程，就是递归不断前进，直到某个list1或list2遍历结束，此时开始拼接，如果list1
        // 遍历完，那就把list2剩下的当做尾巴（最右的一小段），然后返回。然后从右往左，
        // 逐个元素拼接之前递归深入时留下的痕迹。
        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};