(递归)常规解法与分治法

合并k个已排序的链表

http://www.nowcoder.com/questionTerminal/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

1.常规解法,从头到尾两两组合链表

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size() == 0){
            return null;
        }
        ListNode result = lists.get(0);
        for(int i = 1; i < lists.size(); i++) {
            ListNode temp = lists.get(i);
            result = merge(result, temp);
        }
        return result;
    }

    public ListNode merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        }else {
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }

2.常规解法的改进,运用了分治思想的归并组合链表

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size()==0) {
            return null;
        }
        return mergeLists(lists, 0, lists.size()-1);
    }
   public ListNode mergeLists(ArrayList<ListNode> lists,int low, int high) {
        if(low >= high) {
            return lists.get(low);
        }
        int mid = low + ((high-low) >> 1);
        ListNode l1 = mergeLists(lists,low,mid);
        ListNode l2 = mergeLists(lists,mid+1,high);
        return merge(l1, l2);
    }
   public ListNode merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        }else {
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }  
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:10
直接上图
牛客13578115...:改得一般,不值80
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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