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

合并k个已排序的链表

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

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类
     */
    private ListNode merge(ListNode pHead, ListNode qHead) {
        ListNode dummy = new ListNode(-1), i = pHead, j = qHead, pre = dummy;

        while(i != null && j != null) {
            if(i.val > j.val) {
                pre.next = j;
                j = j.next;
            }
            else {
                pre.next = i;
                i = i.next;
            }
            pre = pre.next;
        }

        if(i != null) pre.next = i;
        if(j != null) pre.next = j;
        return dummy.next;
    }

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists.size() == 0) return null;
        if(lists.size() == 1) return lists.get(0);
        if(lists.size() == 2) return merge(lists.get(0), lists.get(1));

        int len = lists.size(), mid = len >> 2;
    
        ArrayList<ListNode> arr = new ArrayList();
        ArrayList<ListNode> arr1 = new ArrayList();
        ArrayList<ListNode> res = new ArrayList();


        arr.addAll(lists.subList(0, mid+1));
        arr1.addAll(lists.subList(mid+1, len));

        res.add(mergeKLists(arr));
        res.add(mergeKLists(arr1));

        return mergeKLists(res);
    }
}

归并排序嘛

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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