【Day 87 】2021-12-05 - 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

[yanglr]

思路:

根据题意, 有点归并、分治的感觉, 可以用堆排序来做。

方法: 堆排序

借助priority_queue, 使用node的val构造一个小顶堆。
创建虚拟头结点，取出最小值对应的结点指针，将其挂接在游标指针上。
只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复。

代码:

实现语言: C++

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return nullptr;

        ListNode* res;
        auto cmp = [](ListNode* n1, ListNode* n2)
        {
            return n1->val > n2->val;
        };

        /* 使用node的val构造一个小顶堆 */
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> nodesQ(cmp);
        for (auto& list : lists)
        {
            if (list != nullptr)
            {
                nodesQ.push(list);
            }
        }

        ListNode* fakeHead = new ListNode(-1);  /* 创建虚拟头结点 */
        ListNode* cur = fakeHead;
        while (!nodesQ.empty()) 
        {
            cur->next = nodesQ.top();  /* 取出最小值对应的结点指针，挂接在游标指针上 */
            cur = cur->next;
            nodesQ.pop();

            if (cur->next != nullptr)  /* 只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复 */
            {
                nodesQ.push(cur->next);
            }
        }
        return fakeHead->next;
    }
};

复杂度分析:

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

[a244629128]

let numsArr = [];
  lists.forEach(item => {
    while(item && item.val !== null) {
      numsArr.push(item.val);
      item = item.next;
    }
  });
  numsArr = numsArr.sort((a, b) => b - a);
  let resultNode = null;
  numsArr.forEach(item => {
    let tempNode = new ListNode(item);
    tempNode.next = resultNode;
    resultNode = tempNode;
  })
  return resultNode;

[Laurence-try]

# 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[ListNode]) -> ListNode:
        lenth = len(lists)

        # basic cases
        if lenth == 0: return None
        if lenth == 1: return lists[0]
        if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])

        # divide and conqure if not basic cases
        mid = lenth // 2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:lenth]))


    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(0)
        c1, c2, c3 = l1, l2, res
        while c1 or c2:
            if c1 and c2:
                if c1.val < c2.val:
                    c3.next = ListNode(c1.val)
                    c1 = c1.next
                else:
                    c3.next = ListNode(c2.val)
                    c2 = c2.next
                c3 = c3.next
            elif c1:
                c3.next = c1
                break
            else:
                c3.next = c2
                break

        return res.next

[ysy0707]

思路：堆排序

class Solution {
    //换一种写法，采用堆排序
    public ListNode mergeKLists(ListNode[] lists) {
        //创建一个堆，重写排序方式
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((o1, o2) -> o1.val - o2.val);
        //遍历链表数组，然后将每个链表的每个节点都放入堆中
        //最小堆会自动的把所有的节点从小到大排列
        for(int i = 0; i < lists.length; i++){
            while(lists[i] != null){
                queue.add(lists[i]);
                //还得把它们连接起来
                lists[i] = lists[i].next;
            }
        }
        //设置虚拟节点
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        //从堆中取出元素并连接起来
        while(!queue.isEmpty()){
            head.next = queue.poll();
            head = head.next;
        }
        head.next = null;
        return dummy.next;
    }
}

时间复杂度: O(NlogN)
空间复杂度: O(N)

[chenming-cao]

解题思路

堆。多路归并问题。建立小顶堆来储存所有非空链表的头节点。建立一个dummy节点来合并链表。每次从小顶堆取值最小的头节点，然后连到合并链表的尾部，之后更新头节点和链表尾部，如果头节点不是null，则放入堆中。如此循环直到堆为空。最后返回合并好的链表的头节点dummy.next即可。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // use min-heap to store the head nodes from the k linked-list, sorted by value of the node
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        // put nodes in heap
        for (ListNode list : lists) {
            // only put non-empty list in the heap
            if (list != null) heap.offer(list);
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!heap.isEmpty()) {
            // get the head with smallest value and connect to the tail of merged list
            ListNode head = heap.poll();
            cur.next = head;
            cur = cur.next;
            // update head to the list and put a new head into heap if the new head is not null
            head = head.next;
            if (head != null) heap.offer(head);
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(knlogk)，k为链表数，k*n为所有链表的总节点数
• 空间复杂度：O(k)，堆中储存k个链表的头节点

[zjsuper]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        elif len(lists) == 1:
            return lists[0]
        elif len(lists) == 2:
            return self.merge_two(lists[0],lists[1])
        
        mid = len(lists)//2
        return self.merge_two(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:]))
    
    def merge_two(self,l1,l2):
        res= ListNode(0)
        c = res

        while l1 and l2:
            if l1.val<=l2.val:
                c.next = ListNode(l1.val)
                c = c.next
                l1= l1.next
            else:
                c.next = ListNode(l2.val)
                c = c.next
                l2 = l2.next
        if l1:
            c.next = l1
        elif l2:
            c.next = l2
        return res.next

[pophy]

思路

• PriorityQueue
  • 如果PQ不空 就依次弹出当前最小值 cur
  • 如果cur.next不空 把cur.next放入PQ

Java Code

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
        ListNode dummy = new ListNode(0);
        for (ListNode node : lists) {
            if (node != null) {
                pq.add(node);
            }
        }
        ListNode p = dummy;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            p.next = cur;
            p = p.next;
            if (cur.next != null) {
                pq.add(cur.next);
            }
        }
        return dummy.next;
    }

时间&空间

• 时间 O(nlog(n))
• 空间 O(n)

[zhangzz2015]

思路

• 利用heap + merge sort实现 k 路合并有序数组，是一个标准的做法，对于非链表类型，有时候要找到第k个，也可采用二分。时间复杂度为O(n logk)，空间复杂度为O(k)。

关键点

代码

• 语言支持：C++

C++ Code:

/**
 * 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 comp = [](ListNode* & node1, ListNode* & node2 ) {return node1->val> node2->val;};         
       priority_queue<ListNode*, vector<ListNode*>, decltype(comp)>  pq(comp);  
        
        for(int i=0;i < lists.size(); i++)
        {
           if(lists[i]) 
            pq.push(lists[i]); 
        }
        ListNode* prev = NULL; 
        ListNode* ret = NULL; 
        while(pq.size())
        {
            ListNode* topNode = pq.top(); 
            pq.pop(); 
            if(prev == NULL)
                ret = topNode; 
            else
                prev->next = topNode; 
            
            if(topNode->next)
                pq.push(topNode->next); 
            
            prev = topNode; 
        }
        
        return ret; 
        
    }
};

[XinnXuu]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge (ListNode[] lists, int l, int r){
        if (l == r){
            return lists[r];
        }
        if (l > r){
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        // if (l1 == null || l2 == null) {
        //     return l1 != null ? l1 : l2;
        // }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode aPtr = l1, bPtr = l2;
        while (aPtr != null && bPtr != null){
            if (aPtr.val < bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        if (aPtr != null){
            tail.next = aPtr;
        } else {
            tail.next = bPtr;
        }
        return dummy.next;
    }
}

[leungogogo]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, (n1, n2) -> {
            if (n1.val > n2.val) {
                return 1;
            } else {
                return -1;
            }
        });
        
        for (int i = 0; i < lists.length; ++i) {
            if (lists[i] != null)
                heap.offer(lists[i]);
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            cur.next = node;
            if (node.next != null) {
                heap.offer(node.next);
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

[skinnyh]

Solution

# 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]:
        dummy = ListNode()
        prev = dummy
        q = []
        for idx, n in enumerate(lists):
            if n:
                heapq.heappush(q, (n.val, idx, n))
        while q:
            _, idx, n = heapq.heappop(q)
            if n.next:
                heapq.heappush(q, (n.next.val, idx, n.next))
            prev.next = n
            prev = n
        return dummy.next

Time complexity: O(NlogK) N is the total number of nodes. K=len(lists)

Space complexity: O(K)

[xj-yan]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        curt = dummy = ListNode(0)
        heap = []
        count = 0
        for node in lists:
            if node is not None:
                count += 1
                heapq.heappush(heap, (node.val, count, node))
        while len(heap) > 0:
            _, _, curt.next = heapq.heappop(heap)
            curt = curt.next
            if curt.next is not None:
                count += 1
                heapq.heappush(heap, (curt.next.val, count, curt.next))
        return dummy.next

Time Complexity: O(nlogn), Space Complexity: O(n)

[littlemoon-zh]

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    memo = {idx: x for idx, x in enumerate(lists)}
    q = [[x.val, idx] for idx, x in  enumerate(lists) if x]
    heapify(q)
    cur = dummy = ListNode(0)
    
    while q:
        _, idx = heappop(q)
        node = memo[idx]
        cur.next = node
        if node.next:
            heappush(q, [node.next.val, idx])
            memo[idx] = node.next
        cur = cur.next
    
    return dummy.next