LeetCode-23 合并K个排序链表

发表于 | 分类于 | 评论数： | 阅读次数：

题目：合并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

思路

这题可以看成是上一题合并两个有序列表）的扩展，可以直接遍历K个链表，然后依次进行两两排序。

实现如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    outNode = ListNode(None)
    curNode = outNode
    while l1 and l2:
        if l1.val < l2.val:
            curNode.next = l1;
            l1 = l1.next
        else:
            curNode.next = l2;
            l2 = l2.next
        curNode = curNode.next
    if l1:
        curNode.next = l1;
    else:
        curNode.next = l2
    return outNode.next

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        tempNode = lists[0]
        for i in range(1, len(lists)):
            tempOutNode = mergeTwoLists(tempNode, lists[i])
            tempNode = tempOutNode
        return tempNode

这里要注意输入为空列表的情况。

优化方法 1

上面的方法在提交运行中，会超时，那么怎么加速一下呢，参考了大神们的解题，可以考虑通过递归的方式，思路如下：

  • 当输入列表长度为0时，直接返回None
  • 当输入列表长度为1时，直接返回列表内容：lists[0]
  • 当输入列表长度为2时，返回这两个列表合并的运算结果：mergeTwoLists(lists[0], lists[1])
  • 当输入的列表长度大于2时，则先取长度的中位数mid，将列表分列两部分:l1 = lists[:mid]，l2=lists[mid:]。然后分别进行递归：self.mergeKLists(l1)，self.mergeKLists(l2)，并将最终递归的结果进行合并。

实现如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    outNode = ListNode(None)
    curNode = outNode
    while l1 and l2:
        if l1.val < l2.val:
            curNode.next = l1;
            l1 = l1.next
        else:
            curNode.next = l2;
            l2 = l2.next
        curNode = curNode.next
    if l1:
        curNode.next = l1;
    else:
        curNode.next = l2
    return outNode.next

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        if len(lists) == 2:
            return mergeTwoLists(lists[0], lists[1])
        tempNode = lists[0]
        mid = len(lists) // 2
        l1 = lists[:mid]
        l2 = lists[mid:]
        return mergeTwoLists(self.mergeKLists(l1), self.mergeKLists(l2))

优化方法 2

其实换一种思路，正所谓不要重复的造轮子，已经有的常用的排序sort()方法其实很高效了，虽然有违算法题的初衷。

思路如下：

  • 遍历所有的列表，把所有的值全部都写入一个list
  • 通过list.sort()进行排序
  • 然后将list转化为ListNode()

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        allList = []
        outNode = ListNode(0)
        curNode = outNode
        for item in lists:
            while item:
                allList.append(item.val)
                item = item.next
        allList.sort()
        for val in allList:
            curNode.next = ListNode(val)
            curNode = curNode.next
        return outNode.next

如果大家有更好的方法，欢迎一起探讨。