题解 | 合并k个已排序的链表

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
        ListNode* Merge(ListNode* head1, ListNode* head2) {
            if(head1 == nullptr) return head2;
            if(head2 == nullptr) return head1;

            ListNode* head = new ListNode(0);
            ListNode* cur = head;
            while(nullptr != head1 && nullptr != head2) {
                if(head1->val <= head2->val) {
                     cur->next = head1;
                     head1 = head1->next;
                }else{
                    cur->next = head2;
                    head2 = head2->next;
                }
                cur = cur->next;
            }
            if(head1 != nullptr) cur->next = head1;
            if(head2 != nullptr) cur->next = head2;
            return head->next;
        }
        ListNode* divide(vector<ListNode*> &lists, int left, int right){
            if (left > right) {
                return nullptr;
            }
            if (left == right) {
                return lists[left];
            }
            int mid = left + (right - left)/2;
            ListNode* l = divide(lists, left, mid);
            ListNode* r = divide(lists, mid + 1 ,right);
            return Merge(l,r);
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            return divide(lists,0, lists.size()-1);
        }
};

(vector<ListNode*>& lists 参数不是一个vextor吗，怎么跟left和right具体的值有关?

这是一个非常好的问题！这触及到了**分治算法（Divide and Conquer）**在实现时的一个核心技巧：通过下标（Index）来划定处理范围，而不是物理切割数组。

简单来说：lists 这个 vector 始终是完整的、没变过的，left 和 right 只是告诉函数：“请只关注 vector 中从下标 left 到下标 right 这一段元素”。

让我们详细拆解一下：

1. 核心概念：下标定义区间

vector<ListNode*>& lists 是一个包含了 $k$ 个链表头的数组。

假设 lists 里有 4 个链表：[L0, L1, L2, L3]。

lists: 始终是 [L0, L1, L2, L3]，从未被修改或切割。
left: 当前任务范围的起始下标。
right: 当前任务范围的结束下标。

2. 模拟执行过程

想象你是项目经理，你要合并这 4 个链表。你不会把这 4 个链表真的剪开分给两个人，而是告诉手下：

初始调用：divide(lists, 0, 3)经理说：“去处理 lists 里从第0个到第3个的所有链表。”计算中间点 mid = (0 + 3) / 2 = 1。经理把任务拆分：给员工 A：divide(lists, 0, 1) （负责左边一半：L0, L1）给员工 B：divide(lists, 2, 3) （负责右边一半：L2, L3）
员工 A 的视角：divide(lists, 0, 1)A 收到指令：“处理下标 0 到 1”。计算中间点 mid = (0 + 1) / 2 = 0。A 继续拆分：给实习生 A1：divide(lists, 0, 0)给实习生 A2：divide(lists, 1, 1)
实习生 A1 的视角（Base Case）：divide(lists, 0, 0)A1 发现 left == right（都是 0）。这意味着：“我只需要负责 1个链表”。关键点来了：A1 直接返回 lists[0] (即 L0)。这就是 vector 和下标发生关系的地方。

3. 为什么要这样做？（性能原因）

如果不使用 left 和 right 下标，我们就必须真的去“切割” vector。

低效的做法（伪代码）：

cpp

// 这种做法非常慢，因为 vector 的拷贝和构建很耗时
ListNode* divide(vector<ListNode*> lists) {
    int n = lists.size();
    if (n == 1) return lists[0];
    
    // 真的创建两个新 vector，把数据拷进去
    vector<ListNode*> leftHalf = lists的前半部分; 
    vector<ListNode*> rightHalf = lists的后半部分;
    
    return mergeTwoLists(divide(leftHalf), divide(rightHalf));
}

高效的做法（当前代码）：

cpp

// 这种做法非常快
// lists 传的是引用 (&)，不发生拷贝，内存里只有一份 lists
ListNode* divide(vector<ListNode*>& lists, int left, int right) {
    // ...
    // 我们只是传了两个整数 (int) 进去，开销极小
    // 通过下标直接访问 lists[left]
}