【Day 87 】2022-10-09 - 23.合并 K 个排序链表

[azl397985856]

23.合并 K 个排序链表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/merge-k-sorted-lists/

前置知识

• 堆
• 链表
• 分而治之

  题目描述

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

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

 

示例 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

[Whisht]

• 动态求极值，使用堆结构。k 个链表，依次从各链表中取表头元素入堆，构建小根堆。

• 取堆顶元素加入新链表表尾，并使指向该堆顶元素所在的链表的指针向后移动一个元素

  class Solution:
  def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
      import heapq
  
      head = ListNode()
      p = head
      heap = []
      for i, pi in enumerate(lists):
          if pi:
              heapq.heappush(heap, (pi.val, i))
              lists[i] = lists[i].next
  
      while heap:
          val, index = heapq.heappop(heap)
          p.next = ListNode(val)
          p = p.next
          if lists[index]:
              heapq.heappush(heap, (lists[index].val, index))
              lists[index] = lists[index].next
      return head.next

[dereklisdr]

class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0){ return null; } ListNode dummy = new ListNode(-1); ListNode cur = dummy;

    PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));

    for (ListNode head : lists){
        if (head != null){
           pq.add(head);
        }
    }

    while(!pq.isEmpty()){
        ListNode node = pq.poll();

        cur.next = node;
        cur = cur.next;

        if (node.next != null){
            pq.add(node.next);
        }
    }
    return dummy.next;

}

}

[LiquanLuo]

/**
 * 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) {
        auto cmp = [](ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;
        };

        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for (auto x : lists) {
            if (x != nullptr) {
                pq.push(x);
            }

        }

        auto head = new ListNode();
        auto cur = head;
        while (!pq.empty()) {
            auto node = pq.top();
            // cout << node->val << endl;
            pq.pop();
            cur->next = node;
            cur = cur->next;
            if (node->next != nullptr) {
                pq.push(node->next);
            }
        }

        return head->next;

    }
};

/**
Constraints:
1. range k: [0, 10e4]
2. range len(list): [0, 500]
3. corner case: empty list

Solution heap:
DS: priority_queue<ListNode>

Algo:
1. maintain a min heap 
2. each time we get the minimum from the heap

Time:O(Nlogk) N = total numbers of nodes, k = lists.length
Space:O(k) k = lists.length
**/

[yang-chenyu104]

采用分治法合并

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]: return self.merge(lists,0,len(lists)-1)

def mergeTwoLists(self, a:ListNode,b:ListNode):
    if not a and b:return b
    if a and not b:return a
    head = ListNode(0)
    tail = head
    p_a, p_b = a, b
    while p_a and p_b:
        if p_a.val <= p_b.val:
            tail.next = p_a
            p_a = p_a.next
        else:
            tail.next = p_b
            p_b = p_b.next
        tail = tail.next
    tail.next = p_a if p_a else p_b
    return head.next

def merge(self,lists:List,l:int,r:int):
    if l == r:
        return lists[l]
    elif l > r:
        return 
    mid = (l + r) // 2
    return self.mergeTwoLists(self.merge(lists,l,mid),self.merge(lists,mid+1,r))

[lbc546]

pq

Python需要hack

from queue import PriorityQueue
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ##ListNode.__lt__ = lambda self, y: True
        head = current = ListNode(0)
        q = PriorityQueue()
        for i, l in enumerate(lists):
            if l:
                q.put((l.val, i, l))

        while not q.empty():
            val, index, node = q.get()
            current.next = ListNode(val)
            current = current.next
            node = node.next
            if node:
                q.put((node.val, index, node))
        return head.next

Complexity

Time: O(nlogk) 还没brute force快

[flaming-cl]

/**
 * 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 {
    // T: O(kn×logk)
    // S: O(logl)
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        return divAndConMerge(lists, 0, n - 1);
    }

    private ListNode divAndConMerge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        return mergeTwoLists(divAndConMerge(lists, left, mid), divAndConMerge(lists, mid + 1, right));
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode();
        ListNode temp = newList;
        while (l1 != null && l2 != null) {
             if (l1.val < l2.val) {
                 temp.next = l1;
                 l1 = l1.next;
             } else {
                 temp.next = l2;
                 l2 = l2.next;
             }
             temp = temp.next;
        }
        temp.next = l1 == null ? l2 : l1;
        return newList.next;
    }
}

[2learnsomething]

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

[cyang258]

/**
 * 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 {
    // T: O(kn×logk)
    // S: O(logl)
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        return divAndConMerge(lists, 0, n - 1);
    }

    private ListNode divAndConMerge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        return mergeTwoLists(divAndConMerge(lists, left, mid), divAndConMerge(lists, mid + 1, right));
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode();
        ListNode temp = newList;
        while (l1 != null && l2 != null) {
             if (l1.val < l2.val) {
                 temp.next = l1;
                 l1 = l1.next;
             } else {
                 temp.next = l2;
                 l2 = l2.next;
             }
             temp = temp.next;
        }
        temp.next = l1 == null ? l2 : l1;
        return newList.next;
    }
}

[MichaelXi3]

idea

优先队列

code

public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (lists==null||lists.size()==0) return null;

    PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
        @Override
        public int compare(ListNode o1,ListNode o2){
            if (o1.val<o2.val)
                return -1;
            else if (o1.val==o2.val)
                return 0;
            else 
                return 1;
        }
    });

    ListNode dummy = new ListNode(0);
    ListNode tail=dummy;

    for (ListNode node:lists)
        if (node!=null)
            queue.add(node);

    while (!queue.isEmpty()){
        tail.next=queue.poll();
        tail=tail.next;

        if (tail.next!=null)
            queue.add(tail.next);
    }
    return dummy.next;
}

}

[Irenia111]

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

[maoting]

思路

归并

代码

const merge2List = (left, right) => {
    let dummyNode = new ListNode();
    let cur = dummyNode;
    while(left && right) {
        if (left.val <= right.val) {
            cur.next = left;
            left = left.next;
            cur = cur.next;
        }
        else {
            cur.next = right;
            right = right.next;
            cur = cur.next;
        }
    }
    cur.next = left ? left : right;
    return dummyNode.next;
}
function mergeLists(lists, start, end) {
    if (start === end) {
        return lists[start]
    }
    const mid = start + ((end - start) >> 1)
    const leftList = mergeLists(lists, start, mid)
    const rightList = mergeLists(lists, mid + 1, end)

    return merge2List(leftList, rightList)
}
var mergeKLists = function(lists) {
    if (lists.length === 0) {
        return null
    }
    return mergeLists(lists, 0, lists.length - 1);
};

复杂度

时间复杂度：O(n∗logk) 空间复杂度：O(logk)

[adamw-u]

class Solution:
    # def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    #     heap = []
    #     d = {}
    #     for k in range(len(lists)):
    #         if lists[k]:
    #             d[k] = lists[k]
    #             # 按照lists[k].va由小到大排序建堆
    #             heap.append((lists[k].val, k))
    #     heapq.heapify(heap)

    #     head = curr = ListNode()
    #     while heap:
    #         _, k = heapq.heappop(heap)
    #         curr.next = d[k]
    #         curr = curr.next
    #         d[k] = d[k].next
    #         if d[k]:
    #             # 在heap中插入(d[k].val, k)
    #             # 按照tuple的第一个元素的大小构建最小堆
    #             heapq.heappush(heap, (d[k].val, k))
    #     curr.next = None
    #     return head.next

    # 两两分治合并
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None 
        n = len(lists)
        return self.merge_sort(lists,0,n-1)

    # 归并法
    def merge_sort(self, lists: List[ListNode], l: int, r: int) -> ListNode:
        if l == r:
            return lists[l]
        mid = (l + r) // 2
        L = self.merge_sort(lists, l, mid)
        R = self.merge_sort(lists, mid + 1, r)
        return self.mergeTwoLists(L, R)

    # 合并两个有序链表
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        prehead = ListNode(0)
        dummy = prehead
        while list1 and list2:
            if list1.val <= list2.val:
                dummy.next = list1
                list1 = list1.next
            else:
                dummy.next = list2
                list2 = list2.next
            dummy = dummy.next
        if list1:
            dummy.next = list1 
        else:
            dummy.next = list2 
        return prehead.next  

复杂度
时间复杂度：O(n∗logk)
空间复杂度：O(logk)

[testplm]

var mergeKLists = function (lists) {
    function mergeTwoLists(l1, l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val<l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1,l2.next );
        return l2;
    }
    if(lists.length == 0) return null;

    while(lists.length > 1) {
        lists.push(mergeTwoLists(lists.shift(), lists.shift()));
    }
    return lists[0];
};

[Xinyi-arch]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        vals = []
        end_flag = 0
        for i in range(len(lists)): # 存储各个链表头节点数据
            if lists[i] != None:
                vals.append(lists[i].val)
            else:
                vals.append(10**4+1)
                end_flag += 1
        if len(vals) == end_flag:# 检查是否全部为空链表
            return None
        min_data = min(vals) # 找到最小值
        b = vals.index(min_data) # 找到最小值对应的指针
        if lists[b].next != None: # 如果对应指针可以推进，那么更新两个list
           lists[b] = lists[b].next
           vals[b] = lists[b].val
        else: # 如果下一位为空，则设定占位符，并增加一个已完结的链表计数
            end_flag += 1 
            vals[b] = 10**4 + 1
        head = ListNode(min_data) # 创建头节点
        now_point = head # 创建滑动节点
        while(end_flag != len(lists)): # 循环执行，知道所有数据均被读取到
            min_data = min(vals)
            b = vals.index(min_data)
            if lists[b].next != None:
                lists[b] = lists[b].next
                vals[b] = lists[b].val
            else:
                end_flag += 1 
                vals[b] = 10**4 + 1
            now_point.next = ListNode(min_data)
            now_point = now_point.next
        return head

[ashleyyma6]

Idea

• merge two by two

Code

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if(n==0){
            return nullptr;
        }
        if(n==1){
            return lists.front();
        }
        while(lists.size()>1){
            vector<ListNode*> newLists;
            for(int i = 0;i+1<lists.size();i+=2){
                ListNode *merged = megerTwo(lists[i], lists[i+1]);
                newLists.push_back(merged);
            }
            if(lists.size() & 0x01){
                newLists.push_back(lists.back());
            }
            lists = vector<ListNode*>(newLists.begin(), newLists.end());
        }
        return lists[0];
    }
private:
    ListNode *megerTwo(ListNode *L1, ListNode *L2){
        ListNode *pre = new ListNode(-1);
        ListNode *head = pre;
        while(L1!=nullptr && L2!= nullptr){
            if(L1->val < L2->val){
                head->next = L1;
                L1 = L1->next;
            }else{
                head->next = L2;
                L2 = L2->next;
            }
            head=head->next;
        }
        if(L1!=nullptr){
            head->next = L1;
        }
        if(L2!= nullptr){
            head->next = L2;
        }
        return pre->next;
    }
};

Complexity Analysis

• Time Complexity:O(kn)
• Space Complexity:O(1)

[aiweng1981]

思路

• 思路描述:好像链表这个数据结构不怎么流行了

代码

#代码
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists):
        '''合并K个有序链表（分治法）'''
        if not lists:
            return None
        n = len(lists)
        interval = 1              # 间隔
        while interval < n:     
            for i in range(0, n-interval, interval*2):
                lists[i] = self.merge2Lists(lists[i], lists[i+interval])
            interval *= 2         # 更新间隔
        return lists[0]

    def merge2Lists(self, l1, l2):
        '''合并两个有序链表'''
        res = cur = ListNode(None)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return res.next

复杂度

• 时间复杂度: O(N**2)
• 空间复杂度: O(N)

[zch-bit]

func MergeKSortedLinkedList(lists []*listnode) *listnode {
    // 1. dummy listnode
    dummyHead := &listnode{val: 0}
    curr := dummyHead

    // 2. push into min heap
    hp := &minHeap{}
    for _, val := range lists {
        *hp = append(*hp, val)
    }
    heap.Init(hp)

    // 3. pop and assign to curr
    for len(*hp) > 0 {
        i := heap.Pop(hp).(*listnode)
        curr.next = &listnode{val: i.val} // create a new listnode
        curr = curr.next

        if i.next != nil {
            heap.Push(hp, i.next)
        }
    }
    return dummyHead.next
}

[AtaraxyAdong]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);
        ListNode headNode = new ListNode();
        ListNode currentNode = headNode;

        for (ListNode list : lists) {
            if (list == null) continue;
            priorityQueue.add(list);
        }

        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            currentNode.next = node;
            currentNode = currentNode.next;
            if (node.next != null) priorityQueue.add(node.next);
        }

        return headNode.next;
    }
}

[Elon-Lau]

class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue priorityQueue = new PriorityQueue<>((node1, node2) -> node1.val - node2.val); ListNode headNode = new ListNode(); ListNode currentNode = headNode;

    for (ListNode list : lists) {
        if (list == null) continue;
        priorityQueue.add(list);
    }

    while (!priorityQueue.isEmpty()) {
        ListNode node = priorityQueue.poll();
        currentNode.next = node;
        currentNode = currentNode.next;
        if (node.next != null) priorityQueue.add(node.next);
    }

    return headNode.next;
}

}

[shiyishuoshuo]

/**
 * 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) {
        int size = lists.length;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // corner case
        if(size == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(size, (a, b) -> {
            return a.val - b.val;
        });

        for (ListNode list: lists){
            if(list != null){
                pq.add(list);
            }
        }

        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            p.next = cur;
            if(cur.next != null){
                pq.add(cur.next);
            }
            p = p.next;
        }

        return dummy.next;                                                 

    }
}

Time: O(Nlog(N)) - where N is the total length of the list node size Space: O(N) - where N is the total length of the list node size

[tian-pengfei]

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        ListNode * head = new ListNode();
        ListNode *current = head;

        auto com = [](ListNode * a,ListNode *b){
            return a->val>b->val;
        };

        priority_queue<ListNode *,vector<ListNode*>, decltype(com)> q(com);

        for (auto & list : lists) {
            if(!list)continue;
            q.push(list);
        }

        while (!q.empty()){
            auto p = q.top();
            q.pop();

            if(p->next){
                q.push(p->next);
            }
            p->next = nullptr;
            current->next = p;
            current = p;
        }

        return head->next;
    }
};

[smz1995]

思路

• 参考题解

代码

# class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode fakeHead = new ListNode(0);
        ListNode temp = fakeHead;

        for (ListNode head: lists)
            if (head != null)
                queue.offer(head);

        while (!queue.isEmpty()) {

            ListNode curr = queue.poll();

            if (curr.next != null)
                queue.offer(curr.next);

            temp.next = curr;
            temp = temp.next;
        }
        return fakeHead.next;
    }
}

[YANGZ001]

LeetCode Link

[Merge k Sorted Lists - LeetCode](https://leetcode.com/problems/merge-k-sorted-lists/)

Idea

Use priorityqueue of size k to store k nodes.

Each time, poll the listnode with least value.

Code

/**
 * 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 == null || lists.length <= 0) return null;
        Queue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode k : lists) {
            if (k == null) continue;
            pq.offer(k);
        }
        ListNode dummy = new ListNode(1);
        ListNode p = dummy;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            if (cur.next != null) pq.offer(cur.next);
            p.next = cur;
            p = p.next;
        }
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity

O(NlogK). For every poll and offer operation of priorityQueue, time complexity would be O(logK). And potentially there would be N-K operation, where N is the sum of length of listNodes.

Space Complexity

O(K) for storing K items into queue.

[luckyoneday]

打卡

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode fakeHead = new ListNode(0);
        ListNode temp = fakeHead;

        for (ListNode head: lists)
            if (head != null)
                queue.offer(head);

        while (!queue.isEmpty()) {

            ListNode curr = queue.poll();

            if (curr.next != null)
                queue.offer(curr.next);

            temp.next = curr;
            temp = temp.next;
        }
        return fakeHead.next;
    }
}

[andyyxw]

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  return lists
    .reduce((p, n) => {
      while (n) {
        p.push(n)
        n = n.next
      }
      return p
    }, [])
    .sort((a, b) => a.val - b.val)
    .reduceRight((p, n) => (n.next = p, n), null)
}

[UCASHurui]

思路

---

用一个小顶底保存每个链表中的最小节点，每次将值最小的节点出堆，加入新的有序链表，并将这个节点的后一个节点入堆，直到堆中没有节点。

代码

---

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        h = []
        for idx, node in enumerate(lists):
            if node: h.append((node.val, idx,node))
        heapq.heapify(h)
        p = new_head = ListNode()
        while h:
            _, idx,node = heapq.heappop(h)
            p.next = node
            p = p.next
            if node.next:
                heapq.heappush(h, (node.next.val, idx,node.next))
        return new_head.next

复杂度分析

---

• 时间复杂度：O(NlogK)
• 空间复杂度：O(K)

[youzhaing]

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1: return l2
        if not l2: return l1
        prehead = ListNode(-1)
        cur = prehead 
        while l1 and l2:
            if l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1 
                l1 = l1.next 
            cur = cur.next 
        if l1: cur.next = l1
        if l2: cur.next = l2
        return prehead.next
    def merge(self, lists, l, r):
        if l == r: return lists[l]
        if l > r: return None 
        mid = (l + r)//2
        l1 = self.merge(lists, l, mid)
        l2 = self.merge(lists, mid + 1, r)
        return self.mergeTwoLists(l1, l2)

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists: return 
        n = len(lists)
        return self.merge(lists, 0 , n - 1)

复杂度

• 时间复杂度：O(knlogk)
• 空间复杂度：O(logk)

[Luckysq999]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

    PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
    ListNode fakeHead = new ListNode(0);
    ListNode temp = fakeHead;

    for (ListNode head: lists)
        if (head != null)
            queue.offer(head);

    while (!queue.isEmpty()) {

        ListNode curr = queue.poll();

        if (curr.next != null)
            queue.offer(curr.next);

        temp.next = curr;
        temp = temp.next;
    }
    return fakeHead.next;
}

}

[MaylingLin]

思路

---

用一个小顶底保存每个链表中的最小节点，每次将值最小的节点出堆，加入新的有序链表，并将这个节点的后一个节点入堆，直到堆中没有节点。

代码

---

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        h = []
        for idx, node in enumerate(lists):
            if node: h.append((node.val, idx,node))
        heapq.heapify(h)
        p = new_head = ListNode()
        while h:
            _, idx,node = heapq.heappop(h)
            p.next = node
            p = p.next
            if node.next:
                heapq.heappush(h, (node.next.val, idx,node.next))
        return new_head.next

复杂度分析

---

• 时间复杂度：O(NlogK)
• 空间复杂度：O(K)

[Hacker90]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
ListNode fakeHead = new ListNode(0);
ListNode temp = fakeHead;

for (ListNode head: lists)
    if (head != null)
        queue.offer(head);

while (!queue.isEmpty()) {

    ListNode curr = queue.poll();

    if (curr.next != null)
        queue.offer(curr.next);

    temp.next = curr;
    temp = temp.next;
}
return fakeHead.next;

} }

[zpc7]

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

[SamLu-ECNU]

思路

建堆，按值将各个链表头进行排序，依次取出值最小的节点构建新链表。

代码

将上述过程转换为完整代码，可知：

# 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]:
        heap = []
        idx = 0
        for l in lists:
            if l:
                heap.append((l.val, idx, l))
                idx += 1

        heapq.heapify(heap)
        dummy = ListNode(-1)
        head = dummy
        while heap:
            val, _, node = heapq.heappop(heap)
            head.next = node
            head = head.next
            if node.next:
                heapq.heappush(heap, (node.next.val, idx, node.next))
                idx += 1
        return dummy.next

复杂度

时间复杂度：$O(nlog(n))$

空间复杂度：$O(n)$

[acoada]

思路

heap

代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        min_heap = []

        for idx, node in enumerate(lists):
            if node is not None:
                heapq.heappush(min_heap, (node.val, idx))

        result, head = None, None

        while min_heap:
            value, index = heapq.heappop(min_heap)
            node = lists[index]

            if not result:
                head = node
                result = node
            else:
                result.next = node
                result = result.next

            lists[index] = lists[index].next

            if lists[index]:
                heapq.heappush(min_heap, (lists[index].val, index))

        return head

复杂度

• Time: O(NKlogK)
• Space: O(K)

[Incipe-win]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        import heapq

        head = ListNode()
        p = head
        heap = []
        for i, pi in enumerate(lists):
            if pi:
                heapq.heappush(heap, (pi.val, i))
                lists[i] = lists[i].next

        while heap:
            val, index = heapq.heappop(heap)
            p.next = ListNode(val)
            p = p.next
            if lists[index]:
                heapq.heappush(heap, (lists[index].val, index))
                lists[index] = lists[index].next
        return head.next

[xxiaomm]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val-b.val);
        ListNode dummy = new ListNode(-1), curr = dummy;
        for (ListNode head: lists) {
            if (head != null)
                pq.add(head);
        }
        while (!pq.isEmpty()) {
            ListNode temp = pq.poll();
            curr.next = temp;
            if (temp.next != null)
                pq.add(temp.next);
            curr = curr.next;
        }

        return dummy.next;
    }
}

[kernelSue]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(((o1, o2) -> o1.val-o2.val));
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null)
                heap.offer(lists[i]);
        }
        if(heap.isEmpty())  return null;
        ListNode head = heap.poll();
        ListNode p = head;
        if(head.next != null)  heap.offer(head.next);
        while(!heap.isEmpty()){
            ListNode top = heap.poll();
            p.next = top;
            p = top;
            if(top.next != null)  heap.offer(top.next);
        }
        return head;
    }
}