大家好，我是魔笑，我来了，我带着链表来了，下面我将一步一步的讲解这道题，也将让你对链表更好的理解，如果你能感叹，链表是这么会事啊。涨见识了，那就太棒了。哈哈，话不啰嗦。直入主题，文章不易，如果对你有帮助，请给一个素质三连，好人一生平安。
题目：
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
? 1->4->5,
? 1->3->4,
? 2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
首先?单链表的定义如下：
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}我们先创建一个升序的单链表，1->3->5：
public ListNode createList(){
ListNode head=new ListNode(0);
ListNode tail=head;
for(int i=1;i<=6;){
tail.next=new ListNode(i);
tail=tail.next;
i=i+2;
}
return head.next;
}解读：我们定义一个ListNode head保存创建的链表,我们需要一个指针?tail?来记录下一个插入位置的前一个位置，接下来，我用图来看看。
图一，首先head和tail都指向0(ListNode@551)：
从图一演变成 图二如下，我们给链表追加元素1,上面tail是指向0(ListNode552)，将tail.next指向1(地址是ListNode552)，再将tail指向1（ListNode552）
?从图二演变成图三，我们接着在链表上追加元素，那么上面tail指向1（ListNode552），那么再将tail.next指向3（ListNode553），再将tail指向3（ListNode552）就是如图。
图四，那么我们得到的链表就是head,我们将0去除，那么就将head=head.next,那么head就是指向1了：
图四变成图五，那么链表就是 1->3->5
?图有点丑，但是意思是这么个意思。先在我们看看如何合并两个链表呢？
public ListNode merge(ListNode list1,ListNode list2) {
ListNode head=new ListNode(0);
ListNode tail=head;ListNode pre1=null;ListNode pre2=null;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
pre1=list1;
tail.next=pre1;
list1=list1.next;
}else{
pre2=list2;
tail.next=list2;
list2=list2.next;
}
tail=tail.next;
}
tail.next=list1==null?list2:list1;
return head.next;
}解释。?同上，我们建立一个head链表，和一个tail，来生成新的链表，然后用两个指针 pre1和?pre2?来记录?list1 和?list2未合并部分的第一位，然后，就是比较listNode1和listNode2连个链表的未合并的第一位的大小，那个链表的未合并的第一位小就将将元素加到head链表上，直到有一个链表合并完了，那么就将剩下的那条链表合并，就Ok了，是不是感觉也不难么。
如果大家想测试两个链表合并，那么我们可以用如下代码去生成两个升序的链表，然后测试自己的代码。不用谢，我就是雷锋。
//生成的链表是1->3->5
ListNode head1=new ListNode(0);
ListNode listNode1=head1;
for(int i=1;i<=6;){
listNode1.next=new ListNode(i);
listNode1=listNode1.next;
i=i+2;
}
head1=head1.next;
//生成的链表是2->4->6
ListNode head2=new ListNode(0);
ListNode listNode2=head2;
for(int i=2;i<=6;){
listNode2.next=new ListNode(i);
listNode2=listNode2.next;
i=i+2;
}
head2=head2.next;那合并多个链表呢，我们先看代码：
public ListNode mergeKLists(ListNode[] listNodes){
ListNode ans=null;
for(int i=0;i<listNodes.length;i++){
ans=merge(ans,listNodes[i]);
}
return ans;
}
public ListNode merge(ListNode list1,ListNode list2) {
ListNode head=new ListNode(0);
ListNode tail=head;ListNode pre1=null;ListNode pre2=null;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
pre1=list1;
tail.next=pre1;
list1=list1.next;
}else{
pre2=list2;
tail.next=list2;
list2=list2.next;
}
tail=tail.next;
}
tail.next=list1==null?list2:list1;
return head.next;
}解释，我们先将ans和ListNode[] listNodes里的每一个链表进行合并，也就变成了两两合并
如果对你有帮助，请给一个素质三连哈