LeetCode-23. Merge k Sorted Lists

221 阅读2分钟

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…