给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例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
解析:
首先合并两个链表的方法,之后用一个变量 ans
来维护以及合并链表,第
public class leetcode23 {
public static void main(String[] args) {
// TODO Auto-generated method stub
ListNode item1= new ListNode(1);
item1.next = new ListNode(4);
item1.next.next = new ListNode(5);
ListNode item2 = new ListNode(1);
item2.next = new ListNode(3);
item2.next.next = new ListNode(4);
ListNode item3 = new ListNode(2);
item3.next = new ListNode(6);
ListNode head = mergeKLists(new ListNode[]{item1,item2,item3});
head.printNode(head);
}
//用一个变量 ans 来维护以及合并的链表,第 i 次循环把第 i 个链表和 ans 合并,答案保存到 ans 中。
public static ListNode mergeKLists(ListNode[] lists){
ListNode ans = null;
for(int i=0;i<lists.length;++i){
ans = mergeTwoLists(ans,lists[i]);
}
return ans;
}
//合并两个链表
public static ListNode mergeTwoLists(ListNode a,ListNode b){
if(a==null||b==null){
return a!=null?a:b;
}
ListNode head = new ListNode(0);
ListNode tail = head,aPtr = a,bPtr = b;
while(aPtr!=null&&bPtr!=null){
if(aPtr.val<bPtr.val){
tail.next = aPtr;
aPtr = aPtr.next;
}else{
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr!=null?aPtr:bPtr);
return head.next;
}
}