题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

输入：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

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

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

解答 & 代码

解法一：K 指针

同合并两个链表的思路，K 个指针同时便利 K 个链表

设有 K 个链表，每个链表最大长度 N

时间复杂度 O()：一共要插入 KN 个节点，每次插入需要比较 K 个节点的大小

空间复杂度 O(K)

/**
* 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) {}
* };
*/
class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
      int listNum = lists.size();    // 链表个数
      if(listNum == 0)            // 特殊情况：如果是0个链表，直接返回空
          return nullptr;

      // curNodes 数组存储当前访问的各链表节点指针，都初始化为 nullptr
      vector<ListNode*> curNodes(listNum, nullptr);
      for(int i = 0; i < listNum; ++i)
      {
          if(lists[i] != nullptr)
              curNodes[i] = lists[i];
      }

      ListNode* dummyHead = new ListNode(-1);    // 合并链表的虚拟头节点
      ListNode* pre = dummyHead;
      // 使用 listNum 个指针同时遍历各链表，每次选取值最小的节点插入合并链表
      while(true)
      {
          int minIdx = -1;
          for(int i = 0; i < listNum; ++i)
          {
              if((minIdx == -1 && curNodes[i] != nullptr) || 
                  (curNodes[i] != nullptr && curNodes[minIdx] != nullptr && curNodes[i]->val < curNodes[minIdx]->val))
                  minIdx = i;                  
          }
          if(minIdx == -1 || curNodes[minIdx] == nullptr)
              break;

          pre->next = curNodes[minIdx];
          pre = pre->next;
          curNodes[minIdx] = curNodes[minIdx]->next;
      }

      return dummyHead->next;    // 返回头节点
  }
};

执行结果： ``` 执行结果：通过

执行用时：1248 ms, 在所有 C++ 提交中击败了 5.10% 的用户内存消耗：12.9 MB, 在所有 C++ 提交中击败了 71.36% 的用户

<a name="hskjf"></a>
## 解法二：顺序合并
从左到右按顺序（两两）合并

- 初始 `result = nullptr` 
- 遍历链表数组，将当前访问到的这个链表和 result 合并

- 时间复杂度 O()
- 空间复杂度 O(1)
```cpp
/**
 * 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) {}
 * };
 */
class Solution {
private:
    // 合并两个链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        if(list1 == nullptr)
            return list2;
        if(list2 == nullptr)
            return list1;

        ListNode* dummyHead = new ListNode(-1);
        ListNode* pre = dummyHead;
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        while(cur1 != nullptr && cur2 != nullptr)
        {
            if(cur1->val < cur2->val)
            {
                pre->next = cur1;
                pre = cur1;
                cur1 = cur1->next;
            }
            else
            {
                pre->next = cur2;
                pre = cur2;
                cur2 = cur2->next;
            }
        }
        if(cur1 != nullptr)
            pre->next = cur1;
        if(cur2 != nullptr)
            pre->next = cur2;

        return dummyHead->next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* result = nullptr;
        for(int i = 0; i < lists.size(); ++i)
            result = mergeTwoLists(result, lists[i]);
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：164 ms, 在所有 C++ 提交中击败了 25.96% 的用户
内存消耗：13 MB, 在所有 C++ 提交中击败了 51.79% 的用户

解法三：分治合并

分治法，将 K 个链表两两配对合并，得到 K/2 个链表，继续两两配对合并，直至合并为一个链表

时间复杂度 O(KN×logK)：第 i 轮合并对链表，每对（两个）链表总长度，因此每轮合并的时间复杂度为 O(KN)，一共 logK 轮合并

空间复杂度 O(logK)：logK 轮合并，因此递归使用的栈空间为 O(logK)

/**
* 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) {}
* };
*/
class Solution {
private:
  // 合并两个链表
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
  {
      if(list1 == nullptr)
          return list2;
      if(list2 == nullptr)
          return list1;

      ListNode* dummyHead = new ListNode(-1);
      ListNode* pre = dummyHead;
      ListNode* cur1 = list1;
      ListNode* cur2 = list2;
      while(cur1 != nullptr && cur2 != nullptr)
      {
          if(cur1->val < cur2->val)
          {
              pre->next = cur1;
              pre = cur1;
              cur1 = cur1->next;
          }
          else
          {
              pre->next = cur2;
              pre = cur2;
              cur2 = cur2->next;
          }
      }
      if(cur1 != nullptr)
          pre->next = cur1;
      if(cur2 != nullptr)
          pre->next = cur2;

      return dummyHead->next;
  }

  // 分治法合并 K 个链表（递归）
  ListNode* mergeLists(vector<ListNode*> lists, int left, int right)
  {
      if(left > right)
          return nullptr;
      if(left == right)
          return lists[left];

      int mid = (left + right) / 2;
      return mergeTwoLists(mergeLists(lists, left, mid), mergeLists(lists, mid + 1, right));
  }
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
      return mergeLists(lists, 0, lists.size() - 1);
  }
};

执行结果： ``` 执行结果：通过

执行用时：316 ms, 在所有 C++ 提交中击败了 11.55% 的用户内存消耗：343.1 MB, 在所有 C++ 提交中击败了 4.99% 的用户


<a name="LkiPM"></a>
## 解法四：优先队列/小根堆
每次合并，应该比较 K 个链表未被合并的最前面的节点的值大小，每次比较 K 个节点，可以用优先队列（小根堆）来存储 K 个节点，每次取 top 就是最小值节点，合并这个节点
> 参考：[leetcode 题解](https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/c-you-xian-dui-lie-liang-liang-he-bing-fen-zhi-he-/)

![优先队列合并链表.gif](https://cdn.nlark.com/yuque/0/2021/gif/1324638/1624439638407-5dde5bc4-db6f-435d-a63d-33efeb016818.gif#clientId=udd0ab64b-20e2-4&from=paste&id=u532fd5b3&margin=%5Bobject%20Object%5D&name=%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E5%90%88%E5%B9%B6%E9%93%BE%E8%A1%A8.gif&originHeight=377&originWidth=723&originalType=binary&ratio=2&size=1825845&status=done&style=none&taskId=u22e32ad6-d5ce-464d-b23b-1140393a9a8)

- 时间复杂度 O(KN×log K)：优先队列中元素不超过 K 个，因此插入和删除时间代价为 O(logK)，一共会处理 KN 个节点
- 空间复杂度 O(K)：优先队列中的元素不超过 K 个
```cpp
/**
 * 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) {}
 * };
 */
class Solution {
private:
    // 小根堆的回调函数
    struct cmp {
        bool operator() (ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> nodeQ;    // 小根堆（优先队列）
        // 初始将每个链表的头节点（如果不为空）存入小根堆
        for(int i = 0; i < lists.size(); ++i)
        {
            if(lists[i] != nullptr)
                nodeQ.push(lists[i]);
        }

        ListNode* dummyHead = new ListNode(-1);
        ListNode* pre = dummyHead;
        while(!nodeQ.empty())
        {
            ListNode* cur = nodeQ.top();
            nodeQ.pop();
            pre->next = cur;
            pre = pre->next;
            if(cur->next != nullptr)
                nodeQ.push(cur->next);
        }

        return dummyHead->next;
    }
};

执行结果：

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了 74.06% 的用户
内存消耗：13 MB, 在所有 C++ 提交中击败了 50.06% 的用户

在牛客网自建小根堆，代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    void adjustHeap(vector<ListNode*>& nodesArr, int start, int end)
    {
        int dadIdx = start;
        int sonIdx = dadIdx * 2 + 1;
        while(sonIdx <= end)
        {
            if(sonIdx + 1 <= end && nodesArr[sonIdx + 1]->val < nodesArr[sonIdx]->val)
                sonIdx += 1;
            if(nodesArr[sonIdx]->val < nodesArr[dadIdx]->val)
            {
                swap(nodesArr[sonIdx], nodesArr[dadIdx]);
                dadIdx = sonIdx;
                sonIdx = dadIdx * 2 + 1;
            }
            else
                return;
        }
    }

    void bulidMinHeap(vector<ListNode*>& nodesArr)
    {
        int size = nodesArr.size();
        for(int i = size / 2 - 1; i >= 0; --i)
            adjustHeap(nodesArr, i, size - 1);
    }

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int k = lists.size();
        if(k == 0)
            return nullptr;

        vector<ListNode*> minHeap;
        for(int i = 0; i < k; ++i)
            if(lists[i] != nullptr)
                minHeap.push_back(lists[i]);
        bulidMinHeap(minHeap);

        ListNode* dummyHead = new ListNode(-1);
        ListNode* pre = dummyHead;
        while(minHeap.size() != 0)
        {
            ListNode* cur = minHeap[0];
            pre->next = cur;
            pre = cur;

            if(cur->next != nullptr)
            {
                minHeap[0] = cur->next;
                adjustHeap(minHeap, 0, minHeap.size() - 1);
            }
            else
            {
                minHeap[0] = minHeap[minHeap.size() - 1];
                minHeap.pop_back();
                adjustHeap(minHeap, 0, minHeap.size() - 1);
            }
        }
        return dummyHead->next;
    }
};

执行结果：通过

执行用时：2 ms, 在所有 C++ 提交中击败了 96.82% 的用户
内存消耗：592 KB, 在所有 C++ 提交中击败了 98.65% 的用户

CodeTop 企业题库

[困难] 23. 合并K个升序链表

题目

解答 & 代码

解法一：K 指针

解法三：分治合并