【LeetCode剑指offer 03】合并两个/K个排序链表

合并两个排序链表

https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

思路

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //两个指针遍历链表，比较，不断把小的那个接到新链表的后面
        //定义dummy,新链表头节点指向dummy
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;

        while(l1 != NULL && l2 != NULL){//当两链表指针都不为空
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{//大于等于的情况
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != NULL ? l1 : l2;//遍历到最后谁不为空就以谁为结尾
        return dummy->next;
    }
};

合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

思路

在合并两个链表的基础上改一下就行

定义一个节点指向空指针，用于充当合成后链表的头节点

遍历所给的链表数组，不断调用合并两个链表时的函数即可

代码

class Solution {
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //两个指针遍历链表，比较，不断把小的那个接到新链表的后面
        //定义dummy,新链表头节点指向dummy
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;

        while(l1 != NULL && l2 != NULL){//当两链表指针都不为空
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{//大于等于的情况
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != NULL ? l1 : l2;//遍历到最后谁不为空就以谁为结尾
        return dummy->next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //创建合并链表的头节点
        ListNode* head = nullptr;//注意，这里不能用ListNode* head = new ListNode();来初始化
        //上述初始化方式会将head指向一个值为0,next为nulptr的节点对象，而我们希望head初始化并且不指向任何对象

        for(int i = 0; i < lists.size(); ++i){
            head = mergeTwoLists(head, lists[i]);
        }
        return head;
    }
};

ListNode* head = nullptr;和ListNode* head = new ListNode();有什么区别？

ListNode* head = nullptr; 定义了一个指针 head，并将其初始化为空指针。此时 head 不指向任何一个节点，即它的值为 nullptr。

ListNode* head = new ListNode(); 定义了一个指针 head，并通过 new 运算符分配了内存来创建一个新的 ListNode 节点。此时 head 指向这个新节点的地址。该节点的值可能是随机的，取决于默认构造函数中的初始化。

总之，两者的区别是一个指针被初始化为空指针，而另一个指针被初始化为指向一个新节点。