【Day 69 】2024-06-15 - 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

[zhiyuanpeng]

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: if not lists or not any([l for l in lists]): return None q = [(s.val, index, s) for index, s in enumerate(lists) if s is not None] cnt = len(q) head = p = ListNode() heapq.heapify(q) while q: , , n = heapq.heappop(q) p.next = ListNode(n.val) n = n.next if n: cnt += 1 heapq.heappush(q, (n.val, cnt, n)) p = p.next return head.next

[Martina001]

类似归并排序，时间复杂度为O（n*klogk） 空间复杂度为递归栈的复杂度：O(logk)

public ListNode mergeKLists(ListNode[] lists) {
        if(null == lists || lists.length == 0){
            return null;
        }
        return mergeK(lists,0,lists.length-1);
    }
    private ListNode mergeK(ListNode[] lists,int l,int r){
        if(l == r){
            return lists[l];
        }
        int mid =(l+r)>>1;
        ListNode lNode = mergeK(lists,l,mid);
        ListNode rNode = mergeK(lists,mid+1,r);
        return mergeTwo(lNode,rNode);
    }
    private ListNode mergeTwo(ListNode a,ListNode b){
        if(null == a){
            return b;
        }
        if(null == b){
            return a;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(a != null && b!= null){
            if(a.val < b.val){
                cur.next = a;
                a = a.next;
            }else{
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }
        if(a != null){
            cur.next = a;
        }
        if(b != null){
            cur.next = b;
        }
        return dummy.next;
    }

[Dtjk]

public ListNode mergeKLists(ListNode a, ListNode b) { if (a == null || b == null) { return a != null ? a : b; } ListNode head = new ListNode(0); ListNode tail = head, aPtr = a, bPtr = b; 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; } tail.next = (aPtr != null ? aPtr : bPtr); return head.next; }

[lxy1108]

# 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]:
        prehead = ListNode()
        pointer = prehead
        while True:
            minnode = None
            minidx = -1
            # print(lists)
            for i,head in enumerate(lists):
                if head is not None:
                    if minnode is None or head.val<minnode.val:
                        minnode = head
                        minidx = i
            if minnode is None:
                break
            pointer.next = minnode
            lists[minidx] = minnode.next
            pointer = pointer.next

        return prehead.next