XingHuiSamaの宝藏之地

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

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

示例 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 = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

感觉我这做法是回去等通知的做法，不过我不管了。复利用了上一题代码，先拼成一个长链表。

1. 算法核心思想：大问题降维化小

这道题需要合并 K 个升序链表。采用了“组件复用”与“顺序累加”的思想。

核心逻辑是：不管有多少个链表，我们始终只做一件事——合并两个有序链表。通过遍历整个数组，让一个初始为空的链表作为“累加器”，依次与数组中的每一条链表进行两两合并。每合并一次，累加器链表就变长一点，直到把所有链表全部合并完毕。

2. 代码逻辑拆解

第一部分：主控调度（mergeKLists）

初始化累加器：先创建一个虚拟节点 p，利用 ListNode* pre = p->next; 初始化出一个空指针 pre，作为后续不断变长的“雪球”本体。
遍历与跳过：使用 for 循环遍历传入的 lists 数组。遇到 lists[i] == NULL 时直接 continue 跳过，防止对空链表进行无效合并。
循环合并：调用 mergeTwoLists，将当前的累加链表 pre 和新遍历到的链表 lists[i] 合并。合并后返回的新链表头部重新赋值给 pre。循环结束后，pre 即为包含所有节点的完整有序链表。

第二部分：基础合并组件（mergeTwoLists）

双指针比较：定义游标 pre1 和 pre2 分别遍历两条链表。创建一个虚拟头节点 result（并用 ans 记录以便返回）。
拉链式交替：在 while 循环中，比较 pre1 和 pre2 当前节点的值，谁的值更小，就让 result->next 指向谁，随后移动对应的游标。
处理尾部：当其中一条链表遍历结束后，跳出循环。直接将另一条尚未遍历完的链表的剩余部分，整块接在 result->next 的后面。
返回结果：返回 ans->next，即去除了虚拟头节点后的真实合并链表头部。

class 合并K个升序链表 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //先合成一条
        ListNode* p = new ListNode(0);
        ListNode* pre = p->next;
        for (int i = 0;i < lists.size();i++) {
            if (lists[i] == NULL) {
                continue;
            }
            pre = mergeTwoLists(pre, lists[i]);
        }

        return pre;

    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {


        ListNode* pre1 = list1;
        ListNode* pre2 = list2;

        ListNode* result =  new ListNode();
        ListNode* ans = result;

        while (pre1!=NULL && pre2!=NULL) {
            if (pre1->val < pre2->val) {
                result->next = pre1;
                pre1 = pre1->next;
                result = result->next;
            }
            else {
                result->next = pre2;
                pre2 = pre2->next;
                result = result->next;
            }
        }

        if (pre1 == NULL) {
            result->next = pre2;
        }
        else {
            result->next = pre1;
        }

        return ans->next;
    }
};

3. 复杂度情况

时间复杂度：合并过程是顺序进行的。设总节点数为 N，由于每次合并都需要将之前已经排好序的节点重新走一遍，整体操作次数与链表数量 K 及节点数相关。
空间复杂度：O(1)。复用了原链表的节点进行指针重组，除了几个固定的指针变量和虚拟头节点外，没有使用额外的线性存储空间。