【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡

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

【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡,暑期算法冲刺,leetcode,链表,算法,原力计划

题目

合并 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
]
将它们合并到一个有序链表中得到。
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

思路

时间复杂度分析:因为允许k的长度为10^4,所以O(n2)是肯定过不去的,可以使用O(nlogn)或者更低,提示中标红处是我们需要注意的地方
解法思路:本题我使用的是暴力解法,首先先将这个链表集合中的所有元素进行合并,生成一个长的链表,因为子链表的长度在500范围内,所以时间复杂度最终会是O(n),同时使用快速排序进行排序,最终时间复杂度在O(nlogn)

代码

先将链表集合中的所有子链表合成一条链表:

 public static ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        for(int  i =0;i<k;i++){
            while(lists[i] != null){
                ListNode temp = lists[i];
                lists[i] = lists[i].next;
                tail.next= temp;
                tail = tail.next;
            }
        }
        return quickSort(dummy.next);
    }

然后对链表进行快速排序:
快速排序思路:设置一个中间值,将小于该值的数放在左边,大于的放在右边
针对本题:设置三个链表,一个存储小于的值,一个存储等于的值,一个存储大于的值

public static  ListNode quickSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pivot = head;
        ListNode lessHead = new ListNode(-1);
        ListNode lessTail = lessHead;
        ListNode biggerHead = new ListNode(-1);
        ListNode biggerTail = biggerHead;
        ListNode equalHead = new ListNode(-1);
        ListNode equalTail = equalHead;

        ListNode current = head;
        while(current != null){
            if(current.val < pivot.val){
                lessTail.next = current;
                lessTail=lessTail.next;
            }else if(current.val > pivot.val){
                biggerTail.next = current;
                biggerTail = biggerTail.next;
            }else{
                equalTail.next = current;
                equalTail = equalTail.next; 
            }
            current = current.next;
        }
        lessTail.next =null;
        biggerTail.next =null;
        equalTail.next = null;
        
        ListNode sortedLess = quickSort(lessHead.next);
        ListNode sortedBigger = quickSort(biggerHead.next);
        return concer(sortedLess,equalHead.next,sortedBigger);
    }

然后分别从小到大,依此添加到链表中:

 public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
        ListNode dummyhead = new ListNode(-1);
        ListNode tail = dummyhead;

        tail.next = less;
        tail = getTail(tail);
        tail.next =euqal ;
        tail = getTail(tail);
        tail.next = bigger;
    

        return dummyhead.next;
    }
    public static ListNode getTail(ListNode head){
        if(head == null){
            return null;
        }
        while(head.next != null){
            head = head.next;
        }
        return head;
    }

我这里使用了最简单的方法,还有很多优质的解法,可以参考力扣中大神的做法。

完整代码:文章来源地址https://www.toymoban.com/news/detail-642410.html

/**
 * 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 {
    //暴力解法
    public static ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        for(int  i =0;i<k;i++){
            while(lists[i] != null){
                ListNode temp = lists[i];
                lists[i] = lists[i].next;
                tail.next= temp;
                tail = tail.next;
            }
        }
        return quickSort(dummy.next);
    }
    public static  ListNode quickSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pivot = head;
        ListNode lessHead = new ListNode(-1);
        ListNode lessTail = lessHead;
        ListNode biggerHead = new ListNode(-1);
        ListNode biggerTail = biggerHead;
        ListNode equalHead = new ListNode(-1);
        ListNode equalTail = equalHead;

        ListNode current = head;
        while(current != null){
            if(current.val < pivot.val){
                lessTail.next = current;
                lessTail=lessTail.next;
            }else if(current.val > pivot.val){
                biggerTail.next = current;
                biggerTail = biggerTail.next;
            }else{
                equalTail.next = current;
                equalTail = equalTail.next; 
            }
            current = current.next;
        }
        lessTail.next =null;
        biggerTail.next =null;
        equalTail.next = null;
        
        ListNode sortedLess = quickSort(lessHead.next);
        ListNode sortedBigger = quickSort(biggerHead.next);
        return concer(sortedLess,equalHead.next,sortedBigger);
    }
    public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
        ListNode dummyhead = new ListNode(-1);
        ListNode tail = dummyhead;

        tail.next = less;
        tail = getTail(tail);
        tail.next =euqal ;
        tail = getTail(tail);
        tail.next = bigger;
    

        return dummyhead.next;
    }
    public static ListNode getTail(ListNode head){
        if(head == null){
            return null;
        }
        while(head.next != null){
            head = head.next;
        }
        return head;
    }
}

到了这里,关于【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 合并K个升序链表(LeetCode 23)

    给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3: Hard。 ★★★★☆ 我们可以想到一种最朴素的方法,依次将链表数组中的链表与最终结果合并。问题便退化成合并两个有序链表。 如何

    2024年01月19日
    浏览(36)
  • LeetCode23.合并K个升序链表

    给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 输入: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 要将多个已按升序排

    2024年02月21日
    浏览(34)
  • Leetcode—23.合并 K 个升序链表【困难】

    用容量为K的最小堆优先队列,把链表的头结点都放进去,然后出队当前优先队列中最小的,挂上链表,,然后让出队的那个节点的下一个入队,再出队当前优先队列中最小的,直到优先队列为空。 之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,

    2024年01月25日
    浏览(52)
  • 2023-09-06力扣每日一题-摆烂暴力

    链接: [1123. 最深叶节点的最近公共祖先](https://leetcode.cn/problems/form-smallest-number-from-two-digit-arrays/) 题意: 如题 解: 今天搞一手暴力,按层存,按层取,直到只取到一个 实际代码: 限制: 树中的节点数将在 [1, 1000] 的范围内。 0 = Node.val = 1000 每个节点的值都是 独一无二 的。

    2024年02月09日
    浏览(36)
  • 2023-08-23力扣每日一题

    链接: 1782. 统计点对的数目 题意: 给n个点和m条无向边(可重复),q个查询 定义 edge[a] 为一个点是a的边数量,定义 ret[a,b] 是 edge[a]+edge[b]-(a与b的边) q个查询q个答案,第i次查询值 val[i] ,求所有的 1=ab=n 条件下有多少 ret[a,b]val[i] 解: TLE卡47了 看了评论区用空间换时间,

    2024年02月10日
    浏览(51)
  • 【力扣每日一题】2023.7.23 接雨水

    目录 题目: 示例: 分析: 代码+运行结果: 接雨水是力扣里非常经典的一道单调栈的题目,使用单调栈的做法就是从左到右将高度依次入栈,保持栈内从栈顶开始升序,在遇到比栈顶更高的高度后,则弹出栈顶元素,并开始按行来计算所积雨水数量,再将后面来的高度入栈

    2024年02月15日
    浏览(26)
  • 力扣每日一题88:合并两个有序数组

    给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并后数组不应由函数返回,而是存储在

    2024年02月07日
    浏览(46)
  • 【力扣每日一题】2023.8.27 合并区间

    目录 题目: 示例: 分析: 代码: 那么合并区间是在什么情况下才能合并呢? 我总结为两种情况 第一种情况就是这样,第二个区间的左区间大于第一个区间的左区间但是小于第一个区间的右区间,并且第一个区间的右区间小于第二个区间的右区间,这种情况下合并的结果就

    2024年02月11日
    浏览(34)
  • 力扣每日一题86:分隔链表

    给你一个链表的头节点  head  和一个特定值   x  ,请你对链表进行分隔,使得所有  小于   x  的节点都出现在  大于或等于   x  的节点之前。 你应当  保留  两个分区中每个节点的初始相对位置。 示例 1: 示例 2: 提示: 链表中节点的数目在范围  [0, 200]  内 -100 = N

    2024年02月07日
    浏览(37)
  • 【力扣每日一题】2023.8.13 合并两个有序数组

    目录 题目: 示例: 分析: 代码: 题目给我们两个升序数组,让我们合并它们,要求合并之后仍然是升序,并且这个合并操作是在数组1原地修改的。数组1的有效数据长度为 m ,而数组1的长度为 m + n,n 是数组2的有效数据长度以及数组的长度。 比较直观容易想到的做法就是

    2024年02月12日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包