BM5题解 | #合并k个已排序的链表#

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

归并排序

这里给的不是好几个headP,而是已经把所有的ListNode都合在一个ArrayList中了,底层的Object[ ]数组中存放了每一个ListNode的引用地址,这些ListNode中都有next指针

因此,可以直接对这个ArrayList使用归并排序

归并排序的具体步骤可以看看这位网友写的博客:https://blog.csdn.net/weixin_45571585/article/details/126239022

两个方法,一个拆sortSection,一个合merge

先说sortSection,递归二分链表,分到每个组只有一个ListNode,就可以开始一层一层返回、组装了。

使用merge组装,内部实现就是个BM3一样,构造一个结果链表,双指针,把val小的加入结果链表中,最后当一条链表遍历完了,另一条还没遍历完的时候,把没遍历完的接在结果链表最后即可。

最后组装好的就是排好序的

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if (lists.size() == 0){
            return null;
        }
        if (lists.size() == 1){
            return lists.get(0);
        }
        return sortSection(lists, 0, lists.size() - 1);
    }

    // 递归拆分
    public ListNode sortSection(ArrayList<ListNode> lists, int start, int end){
        if (start == end) {    // 已经递归分到最后只剩1个了,就返回
            return lists.get(start);
        }
        int mid = (end - start) / 2 + start;
        // [left, mid]
        ListNode left = sortSection(lists, start, mid);
        // [mid + 1, right]
        ListNode right = sortSection(lists, mid + 1, end);
        return merge(left, right);
    }
    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        if (left == null) return right;
        if (right == null) return left;

        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else { // left.val >= right.val
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        // 一条链表先遍历完,另一条就把剩下的接在队尾即可
        cur.next = left == null ? right : left;
        return dummyHead.next;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-18 12:01
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务