【Day 87 】2023-05-11 - 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

[snmyj]

class Solution {
public:
    ListNode* mergetwo(ListNode*a,ListNode*b){
          if ((!a)||(!b)) return a?a:b;
          ListNode head(-1),*rear=&head,*pa=a,*pb=b;
          while(pa&&pb){
              if(pa->val<pb->val){
                  rear->next=pa;
                  pa=pa->next;
              }
              else{
                   rear->next=pb;
                  pb=pb->next;
              }
              rear=rear->next;
          }
          rear->next=(pa?pa:pb);
          return head.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode *ans=nullptr;
            for(int i=0;i<lists.size();i++){
                ans=mergetwo(lists[i],ans);
            }
            return ans;
    }
};

[RestlessBreeze]

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* a, ListNode* b)
    {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for (int i = 0; i < n; i++)
        {
            if (lists[i])
                heap.push(lists[i]);
        }
        ListNode* newHead = new ListNode(0);
        ListNode* temp = newHead;
        while (!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            temp->next = t;
            temp = temp->next;
            if (t->next)
            {
                heap.push(t->next);
            }
        }
        return newHead->next;
    }
};

[kofzhang]

思路

堆实现

复杂度

时间复杂度：O(nmlogn) 空间复杂度：O(n)

代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        heap = []
        for index,node in enumerate(lists):
            if node:
                heapq.heappush(heap,(node.val,index,node))
        while heap:
            _,index,node = heapq.heappop(heap)
            cur.next = node
            cur = node
            if node.next:
                heapq.heappush(heap,(node.next.val,index,node.next))
        return dummy.next

[Diana21170648]

思路

归并

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = 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 = n // 2#归并排序数组分为两半
    return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))

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

**复杂度分析**
- 时间复杂度：O(N)，其中 N 为数组长度。
- 空间复杂度：O(1)

[aoxiangw]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            merge = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                merge.append(self.mergeTwoLists(l1, l2))
            lists = merge
        return lists[0]

    def mergeTwoLists(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        elif l2:
            tail.next = l2
        return dummy.next

[Abby-xu]

import heapq
class Solution: #three lists
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ListNode.__lt__ = lambda self, other: self.val < other.val
        h = []
        head = tail = ListNode(0)
        for i in lists:
            if i: heapq.heappush(h, i)
        while h:
            node = heapq.heappop(h)
            tail.next = node
            tail = tail.next
            if node.next: heapq.heappush(h, node.next)
        return head.next

[zhangyu1131]

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

        // 用堆来求极值
        int n = lists.size();
        vector<ListNode*> heap_vec;
        for (int i = 0; i < n; ++i)
        {
            if (lists[i])
            {
                heap_vec.push_back(lists[i]);
            }
        }
        make_heap(heap_vec.begin(), heap_vec.end(), func);

        ListNode* head = new ListNode(-1);
        ListNode* tmp = head;
        while (!heap_vec.empty())
        {
            ListNode* top = heap_vec[0];
            pop_heap(heap_vec.begin(), heap_vec.end(), func);
            heap_vec.pop_back();
            if (top->next)
            {
                heap_vec.push_back(top->next);
                push_heap(heap_vec.begin(), heap_vec.end(), func);
            }
            top->next = nullptr;
            tmp->next = top;
            tmp = top;
        }

        return head->next;
    }
private:
    static bool func(ListNode*& l1, ListNode*& l2)
    {
        return l1->val > l2->val;
    }
};

[sye9286]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {

    if(lists.length==0)return null;

    const PRE_HEAD = new ListNode();
    let head = PRE_HEAD;

    while (lists.length > 1) {

        let minIndex = 0;

        for (let i = 1; i < lists.length; i++) {
            if (lists[minIndex].val > lists[i].val)
                minIndex = i;
        }

        head.next = lists[minIndex];
        head = head.next;

        if (lists[minIndex].next) lists[minIndex] = lists[minIndex].next;

        else lists.splice(minIndex, 1);
    }

    head.next=lists[0];

    return PRE_HEAD.next;

};

[huizsh]

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

}

[FireHaoSky]

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

思路：分治，归并

代码：python

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        return self.merge(lists, 0, len(lists)-1)

    def merge(self, lists, left, right):
        if left == right:
            return lists[left]

        if left > right:
            return None

        mid = left + (right - left)//2
        return self.mergeTwoLists(self.merge(lists, left, mid), self.merge(lists, mid+1, right))

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

        tail.next = aPtr if aPtr else bPtr
        return head.next

复杂度分析：

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

[harperz24]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        minheap = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(minheap, (lists[i].val, i))
                lists[i] = lists[i].next

        dummy = ListNode()
        cur = dummy
        while minheap:
            val, i = heapq.heappop(minheap)
            cur.next = ListNode(val)
            cur = cur.next
            if lists[i]:
                heapq.heappush(minheap, (lists[i].val, i))
                lists[i] = lists[i].next
        return dummy.next

        # time: O(k * n * logk)
        # space: O(k)

[JasonQiu]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = [(l.val, index) for index, l in enumerate(lists) if l]
        heapq.heapify(heap)
        head = curr = ListNode(None)
        while heap:
            value, index = heapq.heappop(heap)
            curr.next = ListNode(value)
            curr = curr.next
            node = lists[index].next
            lists[index] = lists[index].next
            if node:
                heapq.heappush(heap, (node.val, index))
        return head.next

Time: O(nlogk) Space: O(k)

[wangqianqian202301]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> topNodeList = new ArrayList();
        int endFlag = 0;
        List<ListNode> rtn = new ArrayList<>();
        for(int i = 0; i < lists.length; i++) {
            if(lists[i] == null) {
                continue;
            }

            topNodeList.add(lists[i]);
        }
        int size = topNodeList.size();
        while(endFlag < size) {
            topNodeList.sort((x, y) -> x.val - y.val);
            ListNode min = topNodeList.get(0);
            rtn.add(min);
            if(min.next == null) {
                endFlag ++;
                topNodeList.remove(0);
            }
            else {
                min = min.next;
                topNodeList.set(0, min);
            }
        }
        if(topNodeList.size() > 0 && topNodeList.get(0) != null) {
            ListNode remain = topNodeList.get(0);
            while(remain != null) {
                rtn.add(remain);
                remain = remain.next;
            }
        }
        if(rtn.size() == 0) {
            return null;
        }
        ListNode m = rtn.get(0);
        ListNode t = m;
        for(int i = 1; i < rtn.size(); i++) {
            t.next = rtn.get(i);
            t = t.next;
        }
        return m;
    }
}

[chocolate-emperor]

/**

• 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) {
    ListNode* sentry = new ListNode();
    ListNode* curr = sentry;
    if(lists.size()==0) return nullptr;
    //else if(lists.size()==1)    return lists[0];

    auto cmp = [](const ListNode* a, const ListNode* b){
        return a->val > b->val;
    };
    priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)>pq(cmp);
    //在入队列时保证非空
    int l = lists.size();
    for(int i = 0; i < l; i++){
        if(lists[i])    pq.push(lists[i]);
    }

    while(!pq.empty()){
        ListNode* tmp = pq.top();
        pq.pop();
        curr->next = tmp;
        curr = curr->next;
        if(tmp->next)   pq.push(tmp->next);
    }
    ListNode* head = sentry->next;
    delete sentry;
    sentry = nullptr;
    return head;
}

};

[lp1506947671]

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

复杂度分析

设：每条链表NN个节点，共KK条

时间复杂度：

• 暴力：第一次合并 res 长N（初始化），第二次为2N，以此类推最终复杂度为O((1+2+...+K)*N)=O(\frac{(K+1)*K}{2}*N)，等价于O(K^{2}*N)
• 堆：O(K*N*logK)

空间复杂度：

• 暴力：O(1)
• 堆：O(K)

[Fuku-L]

代码

/**
 * 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 {
    class Status implements Comparable<Status>{
        int val;
        ListNode ptr;
        Status(int val, ListNode ptr){
            this.val = val;
            this.ptr = ptr;
        }
        public int compareTo(Status status2){
            return this.val - status2.val;
        }
    }
    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for(ListNode node: lists){
            if(node != null){
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(!queue.isEmpty()){
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if(f.ptr.next != null){
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}

[SoSo1105]

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: minheap = [] for i in range(len(lists)): if lists[i] : heapq.heappush(minheap, (lists[i].val, i)) lists[i] = lists[i].next

    dummy = ListNode()
    cur = dummy
    while minheap:
        val, i = heapq.heappop(minheap)
        cur.next = ListNode(val)
        cur = cur.next
        if lists[i]:
            heapq.heappush(minheap, (lists[i].val, i))
            lists[i] = lists[i].next
    return dummy.next

[kangliqi1]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

    if (lists == null || lists.length == 0)
        return null;

    ListNode res = null;

    for (int i = 0; i < lists.length; i++)
        res = mergeTwoLists(res, lists[i]);

    return res;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    if (l1 == null || l2 == null)
        return l1 == null ? l2 : l1;

    ListNode fakehead = new ListNode(0), tmp = fakehead;

    while (l1 != null && l2 != null) {

        if (l1.val < l2.val) {

            fakehead.next = l1;
            l1 = l1.next;
        } else {

            fakehead.next = l2;
            l2 = l2.next;
        }

        fakehead = fakehead.next;
    }

    fakehead.next = l1 != null ? l1 : l2;
    return tmp.next;
}

}

[joemonkeylee]

···typescript function mergeKLists(lists: Array<ListNode | null>): ListNode | null { let map = new Map() lists.forEach(head => { while(head){ if(map.has(head.val)){ let temp = map.get(head.val) temp[1].next = head temp[1] = temp[1].next head = head.next }else{ map.set(head.val, [head, head]) head = head.next } } }) let newLists = [...map] if(!newLists.length) return null newLists.sort((a , b) => a[0] - b[0]) newLists.reduce((a, b) => { a[1][1].next = b[1][0] return b }) return newLists[0][1][0] };

[Jetery]

class Solution {
public:
    struct cmp {
        bool operator()(ListNode *a, ListNode *b) {
            return a->val > b->val; // 小根堆
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;

        for (ListNode *list : lists) 
            if (list != nullptr)
                q.push(list);

        ListNode *dummy = new ListNode(0), *tail = dummy;
        while (!q.empty()) {
            ListNode *cur = q.top(); q.pop();
            tail->next = cur;
            tail = tail->next;
            if (cur->next != nullptr) //if (cur->next)
                q.push(cur->next);
        }

        return dummy->next;
    }
};

[Lydia61]

合并有序链表

思路

官方答案

代码

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

[bookyue]

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        return mergeKLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeKLists(ListNode[] lists, int begin, int end) {
        if (begin >= end) return lists[begin];

        int mid = (begin + end) >>> 1;
        ListNode left = mergeKLists(lists, begin, mid);
        ListNode right = mergeKLists(lists, mid + 1, end);
        return mergeList(left, right);
    }

    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode dummny = new ListNode(-1);
        var cur = dummny;

        while (left != null && right != null) {
            if (right.val < left.val) {
                cur.next = right;
                right = right.next;
            } else {
                cur.next = left;
                left = left.next;
            }

            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummny.next;
    }