题目链接： https://leetcode.cn/problems/merge-k-sorted-lists/

视频题解： https://www.bilibili.com/video/BV136421f7hR/

LeetCode 23. 合并 K 个升序链表

题目描述

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

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

举个例子：

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

视频讲解

建议大家点击视频跳转到b站合并 K 个升序链表 (opens new window)观看，体验更佳！

思路解析

方法一 两两合并

假设数组中有4个链表，lists = [[3],[2],[6],[1]]。

1. 对于数组中的链表进行两两合并。比如，链表[3]和[2]合并成[2,3]，链表[6]和[1]合并成[1,6]。
2. 更新lists = [[2,3],[1,6]]。当lists中链表的个数大于1就进入步骤1，否则进入步骤3。
3. 返回lists[0]。

合并过程如下图。

C++代码

/**
 * 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) {
       if (lists.size() == 0) {
           return nullptr;
       }

       while (lists.size() > 1) {
           vector<ListNode*> tempList;
           for (int i = 0; i < lists.size(); i+=2) {
               //每两个链表合并成一个
               ListNode* l1 = lists[i];
               ListNode* l2 = nullptr;
               if (i + 1 < lists.size()) {
                   l2 = lists[i+1];
               }
               tempList.push_back(mergeTwoLists(l1, l2));
           }
           lists = tempList;
       }
       return lists[0];
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //创建一个虚拟的头节点方便后面操作
        ListNode* newHead = new ListNode();
        ListNode* tail = newHead;
        while (list1 && list2) {
            //选取val较小的节点放到tail后面
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            //保证tail一直指向新链表的最后一个节点
            tail = tail->next;
        }
        //把剩下的有序节点挂到tail后面
        if (list1) {
            tail->next = list1;
        } else if (list2) {
            tail->next = list2;
        }
        return newHead->next;
    }
};

java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        List<ListNode> tempList = new ArrayList<>(Arrays.asList(lists));
        while (tempList.size() > 1) {
            List<ListNode> newTempList = new ArrayList<>();
            for (int i = 0; i < tempList.size(); i += 2) {
                ListNode l1 = tempList.get(i);
                ListNode l2 = null;
                if (i + 1 < tempList.size()) {
                    l2 = tempList.get(i + 1);
                }
                newTempList.add(mergeTwoLists(l1, l2));
            }
            tempList = newTempList;
        }
        return tempList.get(0);
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        if (list1 != null) {
            tail.next = list1;
        } else if (list2 != null) {
            tail.next = list2;
        }
        return newHead.next;
    }

}

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None

        while len(lists) > 1:
            tempList = []
            for i in range(0, len(lists), 2):
                # 每两个链表合并成一个
                l1 = lists[i]
                l2 = None
                if i + 1 < len(lists):
                    l2 = lists[i+1]
                tempList.append(self.mergeTwoLists(l1, l2))
            lists = tempList
        return lists[0]

    def mergeTwoLists(self, list1, list2):
        # 创建一个虚拟的头节点方便后面操作
        newHead = ListNode()
        tail = newHead
        while list1 and list2:
            # 选取val较小的节点放到tail后面
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            # 保证tail一直指向新链表的最后一个节点
            tail = tail.next
        # 把剩下的有序节点挂到tail后面
        if list1:
            tail.next = list1
        elif list2:
            tail.next = list2
        return newHead.next

复杂度分析

时间复杂度： O(nlogk)，其中n是合并后链表总的长度，k是链表的个数，两两合并总共需要合并logk次。

空间复杂度： O(k)，会使用临时数组存储两两合并后的新链表。这个是可以优化的，复用已有lists，需要调整lists的大小。

方法二 使用小根堆

本题也可以利用小根堆的特点来解，c++中可以使用优先队列（可以实现堆的操作）。

把链表的节点指针作为优先队列的元素，这里需要实现一个仿函数cmp作为优先队列模板类的参数，用作链表节点的排序。

class cmp {
public:
     bool operator()(ListNode* left, ListNode* right) {
         // 表示根据节点的val值从左到右递减排序
         return left->val > right->val;
     }
 };

假设有k个链表，使用优先队列的算法如下：

1. 把k个链表中未被合并的第一个节点放到优先队列q中。
2. 取优先队列的顶部节点q.top()放入新的链表中，如果(q.top())->next != NULL，就把(q.top())->next放入优先队列。
3. 重复步骤2直至队列q为空。

C++代码

/**
 * 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 cmp {
public:
     bool operator()(ListNode* left, ListNode* right) {
         // 表示根据节点的val值从左到右递减排序
         // 用来实现小根堆
         return left->val > right->val;
     }
 };
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       priority_queue<ListNode*, vector<ListNode*>,cmp> q;
       //把每个链表第一个节点放到队列中
       for (auto list : lists) {
           if (list)
            q.push(list);
       }
       ListNode* head = nullptr;
       ListNode* pIndex = nullptr;
       while (!q.empty()) {
           if (!head) {
               head = q.top();
               pIndex = head;
               q.pop();
           } else if (pIndex) {
               pIndex->next = q.top();
               q.pop();
               pIndex = pIndex->next;
           }
           //把链表中被合并节点的下一个节点放入队列
           if (pIndex && pIndex->next) q.push(pIndex->next);
       }
       if (pIndex)
            pIndex->next = nullptr;
       return head;
    }
};

java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode left, ListNode right) {
            // 表示根据节点的val值从左到右递减排序
            // 用来实现小根堆
            return left.val - right.val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new ListNodeComparator());
        // 把每个链表第一个节点放到队列中
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }
        ListNode head = null;
        ListNode pIndex = null;
        while (!pq.isEmpty()) {
            if (head == null) {
                head = pq.poll();
                pIndex = head;
            } else if (pIndex != null) {
                pIndex.next = pq.poll();
                pIndex = pIndex.next;
            }
            // 把链表中被合并节点的下一个节点放入队列
            if (pIndex != null && pIndex.next != null) {
                pq.offer(pIndex.next);
            }
        }
        if (pIndex != null) {
            pIndex.next = null;
        }
        return head;
    }
}

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        q = []
        # 把每个链表第一个节点放到队列中
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(q, (lists[i].val, i))
        head = ListNode()
        pIndex = head
        while q:
            _, i = heapq.heappop(q)
            pIndex.next = lists[i]
            pIndex = pIndex.next
            if lists[i].next:
                heapq.heappush(q, (lists[i].next.val, i))
                lists[i] = lists[i].next
        return head.next

复杂度分析

时间复杂度： O(nlogk)，其中n是合并后链表总的长度，k是链表的个数，优先队列中节点插入的时间复杂度为O(logk)。

空间复杂度： O(k)，优先队列中最多有k个元素。