⚔ 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%