【LeetCode热题100】【链表】合并 K 个升序链表

叶茂林

发布于 2024-04-23 00:32:53

10500

代码可运行

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

运行总次数：0

代码可运行

题目链接：23. 合并 K 个升序链表 - 力扣（LeetCode）

要合并k个有序链表，其实和合并两个有序链表是一样的

合并两个有序链表是找出较小的节点放在前面，更新节点原来的链表的头节点为后一个节点，递归合并新的两个有序链表

合并k个有序链表同样的思路，先循环找出k个链表里面最小的节点，把这个节点当成头节点，同时更新节点原来的链表的头节点为后一个节点，递归合并新的k个链表

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int min = INT_MAX, index = -1;
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] && lists[i]->val < min) {
                min = lists[i]->val;
                index = i;
            }
        }
        if (index == -1)
            return nullptr;
        ListNode *head = lists[index];
        lists[index] = lists[index]->next;
        head->next = mergeKLists(lists);
        return head;
    }
};