[Leetcode题解]合并K个排序链表

23. 合并K个排序链表

image.png

这个题可以用比较浪费空间但是很简单并且非常快的办法。
将所有的元素拷贝到数组中,然后用内置的sort方法排序,最后建立一个新的链表,拷贝过去。算法复杂度,放入数组和拷贝到链表o(n),,排序(nlogn),总的o(nlogn) 用时击败99.4

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        l = []

        for list in lists:
            while list:
                l.append(list.val)
                list = list.next

        l = sorted(l)

        ans_list = ListNode(-1)
        p = ans_list
        for x in l:
            p.next = ListNode(x)
            p = p.next

        return ans_list.next

评论

暂无评论