【Day 69 】2024-01-23 - 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

[adfvcdxv]

// 21. 合并两个有序链表
var mergeTwoLists = function (list1, list2) {
let dummy = new ListNode(); // 用哨兵节点简化代码逻辑
let cur = dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1; // 把 list1 加到新链表中
list1 = list1.next;
} else { // 注：相等的情况加哪个节点都是可以的
cur.next = list2; // 把 list2 加到新链表中
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 ? list1 : list2; // 拼接剩余链表
return dummy.next;
};

var mergeKLists = function (lists) {
// 合并从 lists[i] 到 lists[j-1] 的链表
function dfs(i, j) {
const m = j - i;
if (m === 0) return null; // 注意输入的 lists 可能是空的
if (m === 1) return lists[i]; // 无需合并，直接返回
const left = dfs(i, i + (m >> 1)); // 合并左半部分
const right = dfs(i + (m >> 1), j); // 合并右半部分
return mergeTwoLists(left, right); // 最后把左半和右半合并
}
return dfs(0, lists.length);
};

[Danielyan86]

Problem: 23. 合并 K 个升序链表

[TOC]

思路

分析题目后发现，每次遍历k个链表的第一个节点后，取最小的一个即可，抽象出来是需要维护一个有序队列，这样每次取队列第一个即可。小根堆刚好满足这个性质。需要注意是val可能想等，这个时后多加一个链表序列参数i参与排序

复杂度

时间复杂度: 取决于小根堆插入排序的效率

$O(nlongn)$

空间复杂度:
需要一个格外的队列装排序node

$O(k)$

Code

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

[snmyj]

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && 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 ? aPtr : bPtr);
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

[larscheng]

思路

分治
将链表拆分为两两1组，一轮合并后链表数量减半
如此往复，最终合并所有的链表

代码

class Solution {

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

        private ListNode spiltAndMerge(ListNode[] lists, int left, int right) {
            if (left == right) {
                return lists[left];
            }
            if (left > right) {
                return null;
            }
            int mid = left + (right - left) / 2;
            ListNode leftNode = spiltAndMerge(lists, left, mid);
            ListNode rightNode = spiltAndMerge(lists, mid + 1, right);
            return merge(leftNode, rightNode);
        }
        private ListNode merge(ListNode leftNode, ListNode rightNode){
            if (leftNode == null) {
                return rightNode;
            }
            if (rightNode == null) {
                return leftNode;
            }
            if (leftNode.val < rightNode.val) {
                leftNode.next = merge(leftNode.next, rightNode);
                return leftNode;
            } else {
                rightNode.next = merge(leftNode, rightNode.next);
                return rightNode;
            }
        }
    }

复杂度

• 时间复杂度：O(nlogk),n为节点个数，k为链表个数
• 空间复杂度：O(logn)

[smallppgirl]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) { 
        int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;
                }
            }
            if (minPointer == -1) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            lists[minPointer] = lists[minPointer].next;
        }
        return dummyHead.next;
    }
}