Costed 2536ms using python, how to optimize?


  • 0
    S

    My code used mergesort and fast-slow pointers to divide the list. I cannot find any time-consuming bottlenecks in my code. But in the distribution I saw a lot of 500ms or even 250ms python solutions. Got confused... Can anyone help me to improve? (I also tried to covert the linked list into an array, sort by built-in method sort() then convert back. This way used 248ms but I believe those python solutions under 2500ms were not all doing it this way)

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def mergeTwoLists(self, l1, l2):
            head = ListNode(0)
            cur = head
            while l1 or l2:
                if l1 and l2 and l1.val < l2.val or not l2:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            return head.next
        
        def sortList(self, head):
            if not head or not head.next: return head
            slow, fast = head, head
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            l1, l2 = head, slow.next
            slow.next = None
            l1 = self.sortList(l1)
            l2 = self.sortList(l2)
            return self.mergeTwoLists(l1, l2)

  • 0
    C

    My python merge sort code, which costs ~1800ms. It's quite strange, why Python code in this case is so costly?

    def sortList(self, head):
        return self.mergeSort(head)
        
    def mergeSort(self, head):
        if not head or not head.next:
            return head
        fast, slow = head.next, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        l1 = self.mergeSort(slow.next)
        slow.next = None
        l2 = self.mergeSort(head)
        return self.merge(l1, l2)
    
    def merge(self, l1, l2):
        dummy = curr = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.