LeetCode 023 Merge k Sorted Lists

LeetCode

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length 0 <= k <= 10^4
0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order. The sum of lists[i].length won’t exceed 10^4.

算法思路：

N/A

注意事项：

1. heap不能比较ListNode大小，要实现lt函数或者将(node.val, node)对加入到heap中(此法Leetcode有编译错误但PyCharm可过)
2. 出堆后node的next赋None不需要，因为每个节点next都会重复赋值，而最后一个节点本来也没有next

Python代码：

ListNode.__lt__ = lambda x, y: x.val < y.val
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        fake_head = ListNode(0)
        for head in lists:
            if head:
                heappush(heap, head)
        it = fake_head
        while heap:
            node = heappop(heap)
            if node.next:
                heappush(heap, node.next)
            # node.next = None
            it.next = node
            it = it.next
        return fake_head.next

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k).

---

算法II解题思路：

Devide and Conquer

注意事项：

1. k.next = None因为删除节点，所以赋None，这句不加也行，但作为良好习惯建议加，且不能在i = i.next前加，否则i会变空。
2. 查lists是否为空

Python代码：

def mergeKLists2(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	return self.merge_sort(lists, 0, len(lists) - 1)

def merge_sort(self, lists, start, end):
	if start >= end:
		return lists[start]
	mid = start + (end - start) // 2
	li = self.merge_sort(lists, start, mid)
	li2 = self.merge_sort(lists, mid + 1, end)
	return self.merge_two_lists(li, li2)

def merge_two_lists(self, li, li2):
	i, j, res = li, li2, ListNode(0)
	k = res
	while i and j:
		if i.val < j.val:
			k.next = i
			i = i.next
			k = k.next
			k.next = None
		else:
			k.next = j
			j = j.next
			k = k.next
			k.next = None
	if i:
		k.next = i
	if j:
		k.next = j
	return res.next

算法分析：

不管多少次递归，每次递归的一层总的节点数为n，而对k做二分，所以递归数为logk, 时间复杂度为O(nlogk)，空间复杂度O(1).

---

算法III解题思路：

算法二的迭代法

注意事项：

1. 输入大小的奇偶处理
2. 返回值是lists[0]而不是lists

Python代码：

def mergeKLists3(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	while len(lists) > 1:
		tmp = []
		if len(lists) % 2 == 1:
			lists.append([])
		for i in range(0, len(lists), 2):
			tmp.append(self.merge_two_lists(lists[i], lists[i + 1]))
		lists = tmp
	return lists[0]

算法分析：

同算法二.