【Day 69 】2021-11-17 - 23. 合并 K 个排序链表

[azl397985856]

23. 合并 K 个排序链表

入选理由

暂无

题目地址

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

前置知识

• 链表
• 归并排序

题目描述

合并  k  个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

[yanglr]

思路:

由于需要将k个升序链表合并成一个升序链表, 可以使用分治来做, 类似于归并排序的做法。

方法: 堆排序

思路: 借助priority_queue, 使用node的val构造一个小顶堆。

创建虚拟头结点，取出最小值对应的结点指针，将其挂接在游标指针上。

只要挂接点后面还有结点，则将其压入queue中，继续从中拿出最小值，循环往复。

代码:

实现语言: C++

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return NULL;
        
        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 != NULL)
            {
                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 != NULL)  /* 只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复 */
            {
                nodesQ.push(cur->next);
            }
        }

        return fakeHead->next;
    }
};

复杂度分析:

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

[zhangzz2015]

• 利用 k 路merge 方法，利用 heap + k merge方法。先把所有list最小/第一个元素放入 最小heap，进行排序，每次pop出最小节点，并放入该节点的下一个节点。注意一些边界情况。时间复杂度为 O(n*logk) n 为所有链表元素总数目，k 为 list 有多少路链表，空间复杂度为O(K)，为heap的大小。

关键点

代码

• 语言支持：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) {}
 * };
 */
struct cmp
{
    bool operator()(ListNode* & node1, ListNode*& node2)
    {
        
        return node1->val > node2->val; 
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq; 
        for(int i=0; i< lists.size(); i++)
        {
            if(lists[i])
              pq.push(lists[i]); 
        }
        if(pq.size()==0)
            return NULL; 
        
        ListNode* ret = pq.top(); 
        ListNode* prev = NULL; 
        while(pq.size())
        {
            ListNode* top = pq.top();
            pq.pop(); 
            if(prev!=NULL)
                prev->next = top; 
            prev = top; 
            if(top->next)
            {
                pq.push(top->next); 
            }
        }
        
        return ret; 
        
    }
};

[kidexp]

thoughts

k路归并

code

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
        merge sort
        """
        if not lists:
            return None

        def merge_two_lists(l1, l2):
            head = current_node = ListNode(0)
            while l1 and l2:
                if l1.val < l2.val:
                    current_node.next = l1
                    l1 = l1.next
                else:
                    current_node.next = l2
                    l2 = l2.next
                current_node = current_node.next
            current_node.next = l1 or l2
            return head.next

        interval = 1
        while interval < len(lists):
            for i in range(0, len(lists), interval * 2):
                lists[i] = merge_two_lists(
                    lists[i], lists[i + interval] if i + interval < len(lists) else None
                )
            interval *= 2
        return lists[0]

complexity

时间复杂度O(nlgk)

空间复杂度O(1)

[biancaone]

from heapq import heappush, heappop
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return None
        
        dummy = tail = ListNode()
        heap = []
        
        for i in range(len(lists)):
            head = lists[i]
            if not head:
                continue
            heappush(heap, (head.val, i, head))
            
        while heap:
            _, index, node = heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heappush(heap, (node.next.val, index, node.next))
                
        return dummy.next

[yachtcoder]

# 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:
        heap = []
        for i, l in enumerate(lists):
            if l: 
                heappush(heap, (l.val, i)) 
        head = ListNode()
        cur = head
        while heap:
            _, i = heappop(heap)
            node = lists[i]
            cur.next = node
            cur = cur.next
            if node.next:
                heappush(heap, (node.next.val, i))
                lists[i] = node.next 
        return head.next

Complexity: O(Llgk); O(k) , L is the total number of nodes in the k linked lists.

[erik7777777]

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!minHeap.isEmpty()) {
            ListNode temp = minHeap.poll();
            cur.next = temp;
            if (temp.next != null) {
                minHeap.offer(temp.next);
            }
            cur = cur.next;
        }
        return dummy.next;
    }
// time O(nlogn) space O(n) 

[yingliucreates]

link:

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

代码 Javascript

function merge (left, right) {
    if (!left) {
        return right;
    } else if (!right) {
        return left;
    } else if (left.val < right.val){
        left.next = merge(left.next, right);
        return left;
    } else {
        right.next = merge(left, right.next);
        return right;
    }
}


function helper(lists, start, end) {
    if (start === end) {
        return lists[start];
    } else if (start < end) {
        const mid = parseInt((start + end) / 2);
        const left = helper(lists, start, mid);
        const right = helper(lists, mid + 1, end);
        return merge(left, right);
    } else {
        return null;
    }
    
}

const mergeKLists = function(lists) {
    return helper(lists, 0, lists.length - 1);
};

[JiangyanLiNEU]

Idea

• priority queue to track the smallest value
• update priority queue when we take one element out
• n = len(lists), m = max(len(list))
• Runtime = O(mlogn), space = O(n)

Python

class Solution(object):
    def mergeKLists(self, lists):
        heap = []
        heapq.heapify(heap)
        for i in range(len(lists)):
            if lists[i]!=None:
                heapq.heappush(heap, [lists[i].val, i])
                lists[i] = lists[i].next
        def getNext():
            if heap == []:
                return None
            else:
                [val, index] = heapq.heappop(heap)
                if lists[index]!=None:
                    heapq.heappush(heap, [lists[index].val, index])
                    lists[index] = lists[index].next
                return ListNode(val, getNext())
        return getNext()

JavaScript

var mergeKLists = function(lists) {
    const q = new MinPriorityQueue({priority: (node) => node.val});
    for (let list of lists){
        list && q.enqueue(list);
    };
    let dummy = new ListNode();
    let cur = dummy
    while(q.size()){
        let list = q.dequeue().element;
        cur.next = new ListNode(list.val);
        cur = cur.next;
        list.next && q.enqueue(list.next);
    };
    return dummy.next;
};

[LareinaWei]

Thinking

Divide and concur.

Code

# 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:
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists)//2
        l1, l2= self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
        return self.merge(l1, l2)
        
    def merge(self, l1, l2):
        head = curr = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return head.next
        

[zjsuper]

Idea: divide and conquer +
Time(O(kn∗logk))

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

[heyqz]

min heap

# 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:
        h = []
        
        for i, li in enumerate(lists):
            if li:
                heappush(h, (li.val, i)) 
        
        dummy = ListNode(0)
        cur = dummy
        
        while h:
            val, i = heappop(h) 
            cur.next = ListNode(val)
            
            if lists[i].next:
                heappush(h, (lists[i].next.val, i))
                lists[i] = lists[i].next
            cur = cur.next
        
        return dummy.next

[RocJeMaintiendrai]

代码

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

复杂度分析

时间复杂度

O(nlogk) k == lists.length

空间复杂度

O(n)

[leo173701]

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(0)
        temp = dummy
        heap = []
        for index,node in enumerate(lists):
            if node:
                heapq.heappush(heap,(node.val, index, node))
        while heap:
            _, curindex, curnode= heapq.heappop(heap)
            temp.next = curnode
            temp = temp.next
            if curnode.next:
                heapq.heappush(heap,(curnode.next.val, index, curnode.next))
        return dummy.next