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

思路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;
    }
}