题目
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
1 2 3 4 5 6 7
| 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
|
思路 + 代码
合并两个有序链表的翻版。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
|
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; if(lists.length==1) return lists[0]; ListNode res = lists[0]; for(int i=1; i<lists.length; i++){ res = mergeTwoLists(res, lists[i]); } return res; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; ListNode prehead = new ListNode(0); ListNode node = prehead; while(l1!=null && l2!=null){ if(l1.val<=l2.val){ node.next = l1; l1=l1.next; }else{ node.next = l2; l2=l2.next; } node = node.next; } node.next=l1==null?l2:l1; return prehead.next; } }
|