Leetcode-23.合并k个排序链表
题目：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
1
2
3
4
5
6
7
| 输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
|
之前还遇到过一题：
合并两个排序链表，返回合并后的排序链表。
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
1
2
| 输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
|
先做合并两个链表的
思路：
- 同时遍历两个链表，比较小的先记下来到新的链表上，被记录下来的链表指针后移。
- 其中一个链表指针为空时，另一链表就是新链表的后一位指向。
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
|
class Solution {
public ListNode mergerTwoList (ListNode l1, ListNode l2) {
ListNode p = new ListNode(0);
ListNode dummy = p;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 == null) p.next = l2;
if (l2 == null) p.next = l1;
return dummy.next;
}
}
|
合并k 个数组也根据以上思路就可以了。
只是要判断数组的各种情况
1）如果是数组里面只有两个 ListNode， 那跟上诉题目一样
2）如果数组大于两个 ListNode， 不断平分数组，把它变成状况（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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution {
public ListNode mergeKLists (ListNode[] lists) {
return divide(lists, 0, lists.length-1);
}
public ListNode divide (listNode[] list, int start, int end) {
if (end == start)
return list[start];
if (end < start)
return null;
if (end - start == 1) {
return mergerTwoList (list[start], list[end]);
}
int mid = start + ((end - start) >> 1);
ListNode left = divide(list, start, mid -1);
ListNode right = divide(list, mid, end);
return mergeTwoList(left, right);
}
public ListNode mergerTwoList (ListNode l1, ListNode l2) {
ListNode p = new ListNode(0);
ListNode dummy = p;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 == null) p.next = l2;
if (l2 == null) p.next = l1;
return dummy.next;
}
}
|
end~
