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

合并k个已排序的链表

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

思路1: 两个两个的合并链表,后面有题友提醒超时了,改进了一下,采用分治法解决

思路2: 分治法,先分,将lists数组分为左右两部分,不断分直到只针对数组一个元素,然后进行合并,两个两个合并。

注意点:

  1. 哨兵节点dummyHead的建立,next指向真正的头结点,这一步可以将头结点的处理合并到其他节点中
  2. dummyHead.next始终指向合并后链表的头结点,然后与lists的链表一个一个进行合并
  3. 初始合并的链表为null

代码如下:

思路1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode dummyHead=new ListNode(-1);
        for(int i=0,len=lists.size();i<len;i++){
            dummyHead.next=mergeTwoLists(dummyHead.next,lists.get(i));//第一次循环即是链表的初始化,指向数组中的第一个链表
        }
        return dummyHead.next;
    }
    //升序合并两个链表
    private ListNode mergeTwoLists(ListNode head1,ListNode head2){
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode dummyHead=new ListNode(-1);
        ListNode cur=dummyHead;
        while(head1!=null&&head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                head1=head1.next;
            }else{
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1==null){
            cur.next=head2;
        }else if(head2==null){
            cur.next=head1;
        }
        return dummyHead.next;

    }
}

思路2:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null||lists.size()==0){
            return null;
        }
        return merge(lists,0,lists.size()-1);
    }
    //分治法的分
    private ListNode merge(ArrayList<ListNode> lists,int left,int right){
        if(left==right){
            return lists.get(left);
        }
        int mid=left+((right-left)>>1);
        return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right));
    }
    
    //升序合并两个链表
    private ListNode mergeTwoLists(ListNode head1,ListNode head2){
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode dummyHead=new ListNode(-1);
        ListNode cur=dummyHead;
        while(head1!=null&&head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                head1=head1.next;
            }else{
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1==null){
            cur.next=head2;
        }else if(head2==null){
            cur.next=head1;
        }
        return dummyHead.next;
    }
}
全部评论

相关推荐

迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
今年读完研的我无房无车无对象,月入还没有过万&nbsp;看到他在朋友圈晒房产证,感叹自己白读了这么多年书
小浪_Coding:学历不代表就能赚多少钱, 自己硕士学历怎么说也是一方面好事, 工作只是为了谋生, 赚钱跟学历不挂钩, 看自己走什么样的路,做什么选择
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

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