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

合并k个已排序的链表

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

1、找中间值,把传入的集合链表分为左右俩部分

2、递归二分这个集合,最后,会得到一个元素不能再分。

3、再利用俩个链表顺序合并的方法,把第一个和第二个不能再分的链表合并,并依次三个和第四个合并。。。

4、最后就得到了k个已排序的链表合并结果。

import java.util.*;

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

public class Solution {

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return mergeKList(lists, 0, lists.size() - 1);
    }

    public ListNode mergeKList(ArrayList<ListNode> lists, int left,int right){
	// 递归终点
        if(left == right){
            return lists.get(left);
        }
        if(left > right){
            return null;
        }
	// 取中间值 >> 1 右移1位表示 / 2^1 
        int mid = left + ((right - left) >> 1);
	// 递归调用到最基础的俩俩合并
	// 分治左右,实现list中的节点元素可以呈树形俩俩合并,实现logn,配合俩俩合并,总时间复杂度nlogn
        return merge(mergeKList(lists,left,mid),mergeKList(lists,mid+1,right));
    }

  
  
    // 俩个链表合并 (基础)
    public ListNode merge(ListNode l1, ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
	// 返回节点
        ListNode dummy = new ListNode(-1);
	// 操作节点
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
	// 补齐剩下未合并完的链
        cur.next = (l1 == null ? l2 : l1);
        return dummy.next;
    }
}

#链表合并#
全部评论

相关推荐

07-25 10:17
仰恩大学 营销
bg双非,被挂了
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
Vincent777...:实习经历可以考虑放上去,对于软件使用方面可以细化一些,比如调整为:熟悉基于LSDYNA的瞬态动力学仿真分析,熟悉基于WORKBENCH的结构拓扑优化
我的简历长这样
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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