将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
思路:采用递归的方法:
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null) return list2; if(list2 == null) return list1; if(list1.val >= list2.val){ list2.next = mergeTwoLists(list1,list2.next); return list2; }else{ list1.next = mergeTwoLists(list1.next, list2); return list1; } } }
|
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
思路 1:采用迭代加递归的方法,将链表数组的链表逐一合并:
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
| class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; if(len == 0){ return null; }else if(len == 1){ return lists[0]; } ListNode ans = lists[0]; for (int i = 1; i < len; i++) { ans = mergeTwoLists(ans, lists[i]); } return ans; }
public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val >= list2.val) { list2.next = mergeTwoLists(list1, list2.next); return list2; } else { list1.next = mergeTwoLists(list1.next, list2); return list1; } } }
|

由于这个算法的时间复杂度为 O(k^2*n),因此运行时间不理想,下面为改进的算法(分治):
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
| class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); }
public ListNode merge(ListNode[] lists, int l, int r) { if (l == r) { return lists[l]; } if (l > r) { return null; } int mid = (l + r) >> 1; return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); }
public 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; } }
|

优化成分治,使得在遍历 lists 时的时间复杂度大大降低:
