23. Merge k Sorted Lists
23. Merge k Sorted Lists
Description
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example
1Input:
2[
3 1->4->5,
4 1->3->4,
5 2->6
6]
7Output: 1->1->2->3->4->4->5->6
Translation
合并k个已排序的链接列表并将其作为一个排序列表返回。分析并描述其复杂性。
Ideas
分治 + 归并排序。将数组进行分支,直到每组有两个链表的时候,把这两个链表进行归并排序。
Note
Accept Code
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) { val = x; }
7 * }
8 */
9public class MergekLists {
10 public ListNode mergeKLists(ListNode[] lists) {
11 if (lists == null || lists.length == 0) {
12 return null;
13 }
14 return divide(0, lists.length - 1, lists);
15 }
16
17 private ListNode divide(int start, int end, ListNode[] listNodes) {
18 if (start == end) {
19 return listNodes[start];
20 }
21 ListNode left = divide(start, (start + end) / 2, listNodes);
22 ListNode right = divide((start + end) / 2 + 1, end, listNodes);
23 return mergeTwoLists(left, right);
24 }
25
26 public ListNode mergeTwoLists(ListNode leftList, ListNode rightList) {
27 if (leftList == null) return rightList;
28 if (rightList == null) return leftList;
29
30 if (leftList.val < rightList.val) {
31 leftList.next = mergeTwoLists(leftList.next, rightList);
32 return leftList;
33 } else {
34 rightList.next = mergeTwoLists(leftList, rightList.next);
35 return rightList;
36 }
37 }
38}
39
转载请注明出处
本文链接:zdran.com/20180329.ht…