Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf9dd130

Browse files
committed
feat: add 023
1 parent66e6d7b commitf9dd130

File tree

4 files changed

+180
-2
lines changed

4 files changed

+180
-2
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,7 @@
7272
|:-------------|:-------------|:-------------|
7373
|4|[Median of Two Sorted Arrays][004]|Array, Binary Search, Divide and Conquer|
7474
|10|[Regular Expression Matching][010]|String, Dynamic Programmin, Backtracking|
75+
|23|[Merge k Sorted Lists][023]|Linked List, Divide and Conquer, Heap|
7576

7677

7778

@@ -124,3 +125,4 @@
124125

125126
[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md
126127
[010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md
128+
[023]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/023/README.md

‎note/023/README.md

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
#[Merge k Sorted Lists][title]
2+
3+
##Description
4+
5+
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
6+
7+
**Tags:** Linked List, Divide and Conquer, Heap
8+
9+
10+
##思路0
11+
12+
题意是合并多个已排序的链表，分析并描述其复杂度，我们可以用分治法来两两合并他们，假设`k`为总链表个数，`N`为总元素个数，那么其时间复杂度为`O(Nlogk)`。
13+
14+
```java
15+
/**
16+
* Definition for singly-linked list.
17+
* public class ListNode {
18+
* int val;
19+
* ListNode next;
20+
* ListNode(int x) { val = x; }
21+
* }
22+
*/
23+
classSolution {
24+
publicListNodemergeKLists(ListNode[]lists) {
25+
if (lists.length==0)returnnull;
26+
return helper(lists,0, lists.length-1);
27+
}
28+
29+
privateListNodehelper(ListNode[]lists,intleft,intright) {
30+
if (left>= right)return lists[left];
31+
int mid= left+ right>>>1;
32+
ListNode l0= helper(lists, left, mid);
33+
ListNode l1= helper(lists, mid+1, right);
34+
return merge2Lists(l0, l1);
35+
}
36+
37+
privateListNodemerge2Lists(ListNodel0,ListNodel1) {
38+
ListNode node=newListNode(0), tmp= node;
39+
while (l0!=null&& l1!=null) {
40+
if (l0.val<= l1.val) {
41+
tmp.next=newListNode(l0.val);
42+
l0= l0.next;
43+
}else {
44+
tmp.next=newListNode(l1.val);
45+
l1= l1.next;
46+
}
47+
tmp= tmp.next;
48+
}
49+
tmp.next= l0!=null? l0: l1;
50+
return node.next;
51+
}
52+
}
53+
```
54+
55+
##思路1
56+
57+
还有另一种思路是利用优先队列，该数据结构用到的是堆排序，所以对总链表个数为`k`的复杂度为`logk`，总元素为个数为`N`的话，其时间复杂度也为`O(Nlogk)`。
58+
59+
```java
60+
/**
61+
* Definition for singly-linked list.
62+
* public class ListNode {
63+
* int val;
64+
* ListNode next;
65+
* ListNode(int x) { val = x; }
66+
* }
67+
*/
68+
classSolution {
69+
publicListNodemergeKLists(ListNode[]lists) {
70+
if (lists.length==0)returnnull;
71+
PriorityQueue<ListNode> queue=newPriorityQueue<>(lists.length,newComparator<ListNode>() {
72+
@Override
73+
publicintcompare(ListNodeo1,ListNodeo2) {
74+
if (o1.val< o2.val)return-1;
75+
elseif (o1.val== o2.val)return0;
76+
elsereturn1;
77+
}
78+
});
79+
ListNode node=newListNode(0), tmp= node;
80+
for (ListNode l: lists) {
81+
if (l!=null) queue.add(l);
82+
}
83+
while (!queue.isEmpty()) {
84+
tmp.next= queue.poll();
85+
tmp= tmp.next;
86+
if (tmp.next!=null) queue.add(tmp.next);
87+
}
88+
return node.next;
89+
}
90+
}
91+
```
92+
93+
94+
##结语
95+
96+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
97+
98+
99+
100+
[title]:https://leetcode.com/problems/merge-k-sorted-lists
101+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎src/com/blankj/easy/_010/Solution.javarenamed to‎src/com/blankj/hard/_010/Solution.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
1-
packagecom.blankj.easy._010;
1+
packagecom.blankj.hard._010;
22

33
/**
44
* <pre>
55
* author: Blankj
66
* blog : http://blankj.com
7-
* time : 2017/04/24
7+
* time : 2017/10/13
88
* desc :
99
* </pre>
1010
*/
Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
packagecom.blankj.hard._023;
2+
3+
importcom.blankj.structure.ListNode;
4+
5+
importjava.util.Comparator;
6+
importjava.util.PriorityQueue;
7+
8+
/**
9+
* <pre>
10+
* author: Blankj
11+
* blog : http://blankj.com
12+
* time : 2017/10/15
13+
* desc :
14+
* </pre>
15+
*/
16+
publicclassSolution {
17+
// public ListNode mergeKLists(ListNode[] lists) {
18+
// if (lists.length == 0) return null;
19+
// return helper(lists, 0, lists.length - 1);
20+
// }
21+
//
22+
// private ListNode helper(ListNode[] lists, int left, int right) {
23+
// if (left >= right) return lists[left];
24+
// int mid = left + right >>> 1;
25+
// ListNode l0 = helper(lists, left, mid);
26+
// ListNode l1 = helper(lists, mid + 1, right);
27+
// return merge2Lists(l0, l1);
28+
// }
29+
//
30+
// private ListNode merge2Lists(ListNode l0, ListNode l1) {
31+
// ListNode node = new ListNode(0), tmp = node;
32+
// while (l0 != null && l1 != null) {
33+
// if (l0.val <= l1.val) {
34+
// tmp.next = new ListNode(l0.val);
35+
// l0 = l0.next;
36+
// } else {
37+
// tmp.next = new ListNode(l1.val);
38+
// l1 = l1.next;
39+
// }
40+
// tmp = tmp.next;
41+
// }
42+
// tmp.next = l0 != null ? l0 : l1;
43+
// return node.next;
44+
// }
45+
46+
publicListNodemergeKLists(ListNode[]lists) {
47+
if (lists.length ==0)returnnull;
48+
PriorityQueue<ListNode>queue =newPriorityQueue<>(lists.length,newComparator<ListNode>() {
49+
@Override
50+
publicintcompare(ListNodeo1,ListNodeo2) {
51+
if (o1.val <o2.val)return -1;
52+
elseif (o1.val ==o2.val)return0;
53+
elsereturn1;
54+
}
55+
});
56+
ListNodenode =newListNode(0),tmp =node;
57+
for (ListNodel :lists) {
58+
if (l !=null)queue.add(l);
59+
}
60+
while (!queue.isEmpty()) {
61+
tmp.next =queue.poll();
62+
tmp =tmp.next;
63+
if (tmp.next !=null)queue.add(tmp.next);
64+
}
65+
returnnode.next;
66+
}
67+
68+
publicstaticvoidmain(String[]args) {
69+
Solutionsolution =newSolution();
70+
ListNode.print(solution.mergeKLists(newListNode[]{
71+
ListNode.createTestData("[1,3,5,7]"),
72+
ListNode.createTestData("[2,4,6]")
73+
}));
74+
}
75+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp