-
Notifications
You must be signed in to change notification settings - Fork 1
/
MergeKSortedLists.java
113 lines (98 loc) · 2.85 KB
/
MergeKSortedLists.java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package com.hncboy;
/**
* @author hncboy
* @date 2019/10/10 17:24
* 23.合并K个排序链表
*
* 给你一个链表数组,每个链表都已经按升序排列。
* 请你将所有链表合并到一个升序链表中,返回合并后的链表。
*
* 示例 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
*
* 示例 2:
* 输入:lists = []
* 输出:[]
*
* 示例 3:
* 输入:lists = [[]]
* 输出:[]
*
* 提示:
* k == lists.length
* 0 <= k <= 10^4
* 0 <= lists[i].length <= 500
* -10^4 <= lists[i][j] <= 10^4
* lists[i] 按 升序 排列
* lists[i].length 的总和不超过 10^4
*
* 通过次数 371,715 提交次数 660,605
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/merge-k-sorted-lists
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class MergeKSortedLists {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
node1.next = new ListNode(4);
node1.next.next = new ListNode(5);
ListNode node2 = new ListNode(1);
node2.next = new ListNode(3);
node2.next.next = new ListNode(4);
ListNode node3 = new ListNode(2);
node3.next = new ListNode(6);
ListNode[] lists = new ListNode[3];
lists[0] = node1;
lists[1] = node2;
lists[2] = node3;
MergeKSortedLists m = new MergeKSortedLists();
System.out.println(m.mergeKLists(lists));
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return solve(lists, 0, lists.length - 1);
}
private ListNode solve(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = (left + right) / 2;
// 合并左右两个链表
return merge(solve(lists, left, mid), solve(lists, mid + 1, right));
}
private ListNode merge(ListNode leftNode, ListNode rightNode) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while (leftNode != null && rightNode != null) {
if (leftNode.val < rightNode.val) {
curr.next = leftNode;
leftNode = leftNode.next;
} else {
curr.next = rightNode;
rightNode = rightNode.next;
}
curr = curr.next;
}
curr.next = leftNode != null ? leftNode : rightNode;
return dummy.next;
}
private static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}