Anyone solve this in Python?

Question

I tried recursive and non-recursive Merge Sort in Python, both TLE in large test case. However using the exact same logic in C++, it accepted.

Is the time limit for python too small? Or anything tricky? Or there exists a better solution?

class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
    def merge(first, second):
        if first.val < second.val:
            listhead=cur=first
            first=first.next
        else:
            listhead=cur=second
            second=second.next

        if first == None:
            cur.next=second
            return listhead
        if second == None:
            cur.next=first
            return listhead

        while first!=None and second!=None :
            if first.val < second.val:
                cur.next = first
                first = first.next
            else:
                cur.next = second
                second = second.next
            cur=cur.next

            if first == None:
                cur.next=second
                break
            elif second == None:
                cur.next=first
                break
        return listhead

    def mergesortrecursive(listhead):
        if listhead == None or listhead.next == None:
            return listhead
        quick=slow=listhead
        quick=quick.next.next
        while quick!=None and quick.next!=None:
            quick=quick.next.next
            slow=slow.next
        second=slow.next
        slow.next=None

        first = mergesortrecursive(listhead)
        second = mergesortrecursive(second)
        return merge(first, second)

    def mergesortnonrecursive(listhead) :
        size=0
        tmp = listhead
        while tmp != None:
            tmp = tmp.next
            size += 1
        n=1
        before = ListNode(0)
        before.next = listhead
        newhead = before
        while n <= size :
            before = newhead
            begin = newhead.next
            while begin != None:
                first = tmp = begin
                for i in range(n-1):
                    if tmp.next != None:
                        tmp = tmp.next
                second = tmp.next
                if second == None:
                    break
                tmp.next = None
                tmp = second
                for i in range(n-1):
                    if tmp.next != None:
                        tmp = tmp.next
                after = tmp.next
                tmp.next = None
                begin = before.next = merge(first, second)
                while begin.next != None:
                    begin = begin.next
                begin.next = after
                before = begin
                begin = after
            n *= 2
        return newhead.next

    return mergesortnonrecursive(head)

Answer 1

AC with time 5800+ ms，I use InsertSort optimize the MergerSort. Try a few times more,it will AC.

# coding=utf-8
__author__ = 'st316'
'''
Sort a linked list in O(n log n) time using constant space complexity.
'''
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def toString(self):
        cur = self
        s = ''
        while cur.next:
            s += str(cur.val) + ' -> '
            cur = cur.next
        return s + str(cur.val)


class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if not head:
            return head
        head = self.preInsertSort(head)
        #print head.toString()
        i = 4
        while True:
            h = ListNode(0)
            h.next = head
            cur = head
            m = 0
            hh = h
            while True:
                m += 1
                p = cur
                if not p:
                    break
                for j in xrange(1, i):
                    cur = cur.next
                    if not cur or not cur.next:
                        break
                if cur:
                    q = cur.next
                    cur.next = None
                else:
                    q = None
                cur = q
                if not q:
                    h.next = p
                    break
                for j in xrange(1, i):
                    if not cur.next:
                        break
                    cur = cur.next
                tmp = cur.next
                cur.next = None
                cur = tmp
                h.next, h = self.mergePQ(p, q)
            head = hh.next
            i *= 2
            if m <= 1:
                return head
        return None

    def mergePQ(self, p, q):
        if p.val < q.val:
            head = p
            head1 = p.next
            head2 = q
        else:
            head = q
            head1 = p
            head2 = q.next
        h = head
        while head1 and head2:
            if head1.val < head2.val:
                head.next = head1
                head1 = head1.next
            else:
                head.next = head2
                head2 = head2.next
            head = head.next
        if head1:
            head.next = head1
        elif head2:
            head.next = head2
        while head.next:
            head = head.next
        return h, head

    def preInsertSort(self, l):
        k = 4  # 当前要处理子串的长度
        cur = l.next  # 当前要处理的节点
        curHead = l  # 当前要处理子串的头节点
        i = 1  # 计数，记录当前字串已经有序的节点数
        pre = None  # 当前对比节点的前一个节点
        pre1 = l  # 当前处理的节点的前一个节点
        while cur:
            if i == k:  # 当前字串是否已经处理完
                curHead = cur
                pre = pre1
                pre1 = cur
                cur = cur.next
                i = 1
            tmp1 = pre # 记录上一个有序子序列的尾节点
            j = 0
            c = curHead  # 当前对比的节点
            f = True
            while j < i:
                if not cur or not c:
                    break
                if cur.val >= c.val:  # 继续找位置
                    pre = c
                    c = c.next
                    j += 1
                else:  # 插入合适位置
                    pre1.next = cur.next
                    cur.next = c
                    if pre:
                        pre.next = cur
                    else:
                        l = cur
                    if j == 0:
                        curHead = cur
                        pre = tmp1
                    else:
                        pre = tmp1
                    i += 1
                    cur = pre1.next
                    f = False
                    break
            if f and j == i:  # 位置不用调整
                pre = tmp1
                pre1 = cur
                cur = cur.next
                i += 1
        return l