⚔ LeetCode | 23. Merge K Sorted Lists

Problem

LeetCode 23. Merge k Sorted Lists

Difficulty : Hard

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

Analysis

这道题题意是需要我们合并多个链表,和一般的归并操作不同的是,他给出来的每一条链表都是不定长的,而且链表的数量也是不一定的,但实际上还是换汤不换药。依旧可以使用类似于归并排序的归并操作来解之。

Approach 1

一般的归并操作只能在将两个链表合并成一个链表,这里提供了任意数量的链表,那么我们就需要分情况进行处理。

一般可以分为以下几种情况:

  • 链表数量为0:直接返回空
  • 链表数量为1:直接返回数组中第一个(也是唯一的一个)链表
  • 链表数量为2:进行合并操作,将两个链表合并成一个
  • 链表数量大于2:将链表划分成两半,进行递归处理

而合并操作也是很普通的操作:

对于两个链表,用两个指针指向链表的头

如果两个链表都不为空,那么就将指针所指元素较小的值放到新的链表中

然后将剩余的一个链表的头接上新的链表的尾巴

这样就产生了一个有序的新的链表了

代码如下:

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

func mergeKLists(lists []*ListNode) *ListNode {
count := len(lists)
if count == 0 {
return nil
} else if count == 1 {
return lists[0]
} else if count == 2 {
res := new(ListNode)
current := res
la := lists[0]
lb := lists[1]
if la == nil && lb == nil {
return nil
}
for la != nil && lb != nil {
if current.Next != nil {
current = current.Next
}
if la.Val < lb.Val {
current.Val = la.Val
la = la.Next
} else {
current.Val = lb.Val
lb = lb.Next
}
current.Next = new(ListNode)
}
for la != nil {
if current.Next != nil {
current = current.Next
}
current.Val = la.Val
current.Next = new(ListNode)
la = la.Next
}
for lb != nil {
if current.Next != nil {
current = current.Next
}
current.Val = lb.Val
current.Next = new(ListNode)
lb = lb.Next
}
current.Next = nil
return res
} else {
return mergeKLists([]*ListNode{mergeKLists(lists[:count/2]), mergeKLists(lists[count/2:])})
}
}

这段代码使用了递归的思想,将多个链表合并成一个。将两个有序的链表合并成一个的时间复杂度为O(n),假设有k个链表,那么将所有的链表都合并成一个则需要$O(\sum_{i=0}^{log_2k}N) $的时间复杂度。因此时间复杂度为O(nlogk)

优化

超越了 LeetCode 上76.47 %的提交,因此还有不少的提高空间。从算法上看应该是复杂度比较小的,那么问题就应该出现在归并的操作上。可以看出,最后归并的时候是重新生成节点并且复制,那么可以考虑改成直接将剩余的链表的头接到当前链表的尾巴上,这样对于很多合并都节省了一大部分操作。而且,如果把递归改成迭代的写法,那么运行时间应该会再快上一点

改进后的代码如下:

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
func mergeKLists(lists []*ListNode) *ListNode {
l := len(lists)
if l == 0 {
return nil
}
step := 1
for step < l {
for i := 0; i+step < l; i += step * 2 {
lists[i] = merge(lists[i], lists[i+step])
}
step = step * 2
}
return lists[0]
}

func merge(l1, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
head, last := l1, l1
if l1.Val > l2.Val {
head, last = l2, l2
l2 = l2.Next
} else {
l1 = l1.Next
}

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
last.Next = l1
l1 = l1.Next
} else {
last.Next = l2
l2 = l2.Next
}
last = last.Next
}
if l1 == nil {
last.Next = l2
}
if l2 == nil {
last.Next = l1
}

return head
}

这种写法虽然时间复杂度和上面的是一样的,但是在操作上比上面要快上不少,大概可以提高40%的性能。

Summary

这道题虽然还是被 LeetCode 标记为Hard,但是本质上还是最普通的归并操作,这样算法应该是属于非常基础的算法,至于为什么是Hard,这就不太搞得懂了。

土豪通道
0%