Merge k Sorted Lists

Merge k Sorted Lists

描述

给定 k 个有序链表, 合并他们并返回头节点

示例:
输入 : [(2 -> 3 -> 4), (5 -> 6 -> 7)]
输出 : (2 -> 3 -> 4 -> 5 -> 6 -> 7)

分析

merge 两个有序链表的复杂度是 , 每次合并只会降低一个链表数量, 看起来一个个合并就行, 但是如果逐个合并, 在合并过程中, 其中一个链表会越来越大, 导致复杂度实际变大, 也不能通过 oj, 应该先两两合并, 对合并完成的再两两合并, 降低每次合并的链表长度

答案

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    def mergeList(self, m, n):
        if m is None:
            return n
        if n is None:
            return m
        x = m
        y = n
        root = m
        xp = None
        yp = y
        while True:
            if y is None:
                break
            if x is None:
                xp.next = y
                break
            if x.val <= y.val:
                xp = x
                x = x.next
            else:
                ystart = y
                while True:
                    if y is not None and root.val > y.val:
                        root = y
                    if y is not None and x.val > y.val:
                        yp = y
                        y = y.next
                    else:
                        if xp is None:
                            yp.next = x
                            xp = yp
                        else:
                            xp.next = ystart
                            xp = yp
                            yp.next = x
                        break
        return root

    """
    @param lists: a list of ListNode
    @return: The head of one sorted list.
    """
    def mergeKLists(self, lists):
        if len(lists) == 0:
            return None
        while True:
            if len(lists) == 1:
                break
            tmp = []
            i = 0
            while True:
                if i >= len(lists):
                    break
                if (i + 1) >= len(lists):
                    tmp.append(lists[i])
                    break
                else:
                    tmp.append(self.mergeList(lists[i], lists[i + 1]))
                i += 2
            lists = tmp
        return lists[0]
打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~