LeetCode 23 合并 K 个升序链表

这篇具有很好参考价值的文章主要介绍了LeetCode 23 合并 K 个升序链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 23 合并 K 个升序链表

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-k-sorted-lists/description/

博主Github:https://github.com/GDUT-Rp/LeetCode

LeetCode 23 合并 K 个升序链表,leetcode,链表,算法

题目:

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例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 <= 1 0 4 10^4 104
  • 0 <= lists[i].length <= 500
  • − 1 0 4 -10^4 104 <= lists[i][j] <= 1 0 4 10^4 104
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

解题思路:

方法一:顺序合并

用一个变量 ans 来维护以及合并的链表,第 i 次循环把第 i 个链表和 ans 合并,答案保存到 ans 中。

Golang
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    var ans *ListNode
    for i:=0; i<len(lists); i++ {
        ans = mergeTwoLists(ans, lists[i])
    }
    return ans
}

func mergeTwoLists(a *ListNode, b *ListNode) *ListNode {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }

    var head ListNode
    tail := &head

    for (a != nil && b != nil) {
        if a.Val < b.Val {
            tail.Next = a
            a = a.Next
        } else {
            tail.Next = b
            b = b.Next
        }
        tail = tail.Next
    }

    if a != nil {
        tail.Next = a
    } else {
        tail.Next = b
    }
    return head.Next
}
C++
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;
    }
};
Java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(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;
    }
}

复杂度分析

时间复杂度: 假设每个链表的最长长度是 n。在第一次合并后,ans 的长度为 n;第二次合并后,ans 的长度为 2n,第 i 次合并后,ans 的长度为 i×n。第 i 次合并的时间代价是 O(n+(i−1)×n)=O(i×n),那么总的时间代价为 O ( ∑ i = 1 k ( i × n ) ) = O ( ( 1 + k ) ⋅ k 2 × n ) = O ( k 2 n ) O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n) O(i=1k(i×n))=O(2(1+k)k×n)=O(k2n),故渐进时间复杂度为 O ( k 2 n ) O(k^2 n) O(k2n)

空间复杂度 O(1) 。

方法二:分治合并

考虑优化方法一,用分治的方法进行合并。

  • 将 kkk 个链表配对并将同一对中的链表合并;
  • 第一轮合并以后, k 个链表被合并成了 k 2 \frac{k}{2} 2k​ 个链表,平均长度为 2 n k \frac{2n}{k} k2n,然后是 k 4 \frac{k}{4} 4k 个链表, k 8 \frac{k}{8} 8k 个链表等等;
  • 重复这一过程,直到我们得到了最终的有序链表。

LeetCode 23 合并 K 个升序链表,leetcode,链表,算法

Golang
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    return merge(lists, 0, len(lists) - 1)
}

func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    if left > right {
        return nil
    }
    mid := (left + right) >> 1
    return mergeTwoLists(merge(lists, left, mid), merge(lists, mid+1, right))
}

func mergeTwoLists(a *ListNode, b *ListNode) *ListNode {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }

    var head ListNode
    tail := &head

    for (a != nil && b != nil) {
        if a.Val < b.Val {
            tail.Next = a
            a = a.Next
        } else {
            tail.Next = b
            b = b.Next
        }
        tail = tail.Next
    }

    if a != nil {
        tail.Next = a
    } else {
        tail.Next = b
    }
    return head.Next
}
C++
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* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};
Java
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[l];
        }
        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 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;
    }
}

时间复杂度:考虑递归「向上回升」的过程——第一轮合并 k 2 \frac{k}{2} 2k 组链表,每一组的时间代价是 O ( 2 n ) O(2n) O(2n);第二轮合并 k 4 \frac{k}{4} 4k​ 组链表,每一组的时间代价是 O ( 4 n ) O(4n) O(4n)…所以总的时间代价是 O ( ∑ i = 1 ∞ k 2 i × 2 i n ) = O ( k n × log ⁡ k ) O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k) O(i=12ik×2in)=O(kn×logk),故渐进时间复杂度为 O ( k n × log ⁡ k ) O(kn \times \log k) O(kn×logk)
空间复杂度:递归会使用到 O ( log ⁡ k ) O(\log k) O(logk) 空间代价的栈空间。

方法三:使用优先队列/最小堆合并

这个方法和前两种方法的思路有所不同

我们需要维护当前每个链表没有被合并的元素的最前面一个, k k k 个链表就最多有 k k k 个满足这样条件的元素,每次在这些元素里面选取 val 属性最小的元素合并到答案中。

在选取最小元素的时候,我们可以用优先队列/最小堆来优化这个过程。

Golang
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

import "container/heap"

type Status struct {
    Val  int
    Ptr  *ListNode
}

type PriorityQueue []*Status

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Status))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    *pq = old[0 : n-1]
    return item
}

func mergeKLists(lists []*ListNode) *ListNode {
    var q PriorityQueue
    heap.Init(&q)

    for _, node := range lists {
        // 每个链表第一个都放进这个堆
        if node != nil {
            heap.Push(&q, &Status{Val: node.Val, Ptr: node})
        }
    }

    var head ListNode
    tail := &head

    for q.Len() > 0 {
        // 取出最小的
        f := heap.Pop(&q).(*Status)
        tail.Next = f.Ptr
        tail = tail.Next
        // 只要所取的节点后面还要数据
        if f.Ptr.Next != nil {
            // 就放进堆里来
            heap.Push(&q, &Status{Val: f.Ptr.Next.Val, Ptr: f.Ptr.Next})
        }
    }

    return head.Next
}
Java
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;
    }
}
C++
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;
    }
};

复杂度分析

时间复杂度:考虑优先队列中的元素不超过 k k k 个,那么插入和删除的时间代价为 ¥O(\log k)$,这里最多有 k n kn kn 个点,对于每个点都被插入删除各一次,故总的时间代价即渐进时间复杂度为 O ( k n × log ⁡ k ) O(kn \times \log k) O(kn×logk)
空间复杂度:这里用了优先队列,优先队列中的元素不超过 k k k 个,故渐进空间复杂度为 O ( k ) O(k) O(k)文章来源地址https://www.toymoban.com/news/detail-690387.html

到了这里,关于LeetCode 23 合并 K 个升序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-08-12 LeetCode每日一题(合并 K 个升序链表)

    点击跳转到题目位置 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3:

    2024年02月13日
    浏览(41)
  • 23. 合并 K 个升序链表(递归分治)

    这是我的第一个自己ak的分治题目!!!好耶!!(骄傲脸 思路参考:148. 排序链表(归并排序)

    2024年01月16日
    浏览(35)
  • 【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡

    合并 K 个升序链表 难度: 困难 描述: 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 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 ] 将它们合并到一个有序

    2024年02月13日
    浏览(36)
  • Leetcode算法递归类—合并两个有序链表

    目录 21. 合并两个有序链表 题解: 代码: 将两个升序链表合并为一个新的  升序  链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例 1: 示例 2: 示例 3: 提示: 两个链表的节点数目范围是  [0, 50] -100 = Node.val = 100 l1  和  l2  均按  非递减顺序  

    2024年02月13日
    浏览(39)
  • LeetCode 21.合并两个有序链表

    题目链接 👉 LeetCode 21.合并两个有序链表👈 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 取小的进行尾插 👇 图解 👇 取小的进行尾插 👇 图解 👇 🥰 希望烙铁们能够理解欧! 总结🥰 以上就是本题讲解的全部内

    2024年02月13日
    浏览(51)
  • Leetcode 21. 合并两个有序链表

    题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/ 两个链表都是升序链表,新建一个链表,引入伪头节点作为辅助节点,将各节点添加到伪节点之后,再用一个cur节点指向新链表的末尾 遍历两个链表,对比每个节点值,将更小的链表节点加入到新链表中 如果其中一

    2024年02月13日
    浏览(47)
  • LeetCode21.合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 : 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 创建一个新的链表头节点(dummyNode)和一个指针current,用于表示当前节点。 在一个while循环中,比较两个链表的节

    2024年02月20日
    浏览(42)
  • 【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

      目录 一.【Leetcode206】反转链表 1.链接 2.题目再现  3.解法A:三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现  3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现  3.解法 1.链接 反转链表 2.题目再现  3.解法

    2024年02月02日
    浏览(50)
  • Leetcode-每日一题【1669.合并两个链表】

    给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。 请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。 下图中蓝色边和节点展示了操作后的结果:   请你返回结果链表的头指针。 示例 1: 输入: list1 = [0,1,2,3,4,5], a = 3, b

    2024年02月13日
    浏览(50)
  • 【Leetcode刷题】链表的中间结点和合并两个有序链表

    生命如同寓言,其价值不在与长短,而在与内容。                                ——塞涅卡 目录 一.链表的中间结点 1.快慢指针 二.合并两个有序链表  1.尾插法 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点

    2023年04月17日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包