Why did I get a TLE? it is supposed to be O(n^2)


  • 0
    S
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head:
                return None
            min_node = ListNode(-1)
            min_node.next = head
            node = head
            while node.next:
                root = min_node
                while root != node and root.next.val < node.next.val:
                    root = root.next
                if root != node:
                    temp = node.next
                    node.next = node.next.next
                    temp.next = root.next
                    root.next = temp
                    
                else:
                    node = node.next
                
            return min_node.next

  • 0
    G

    The reason of Time Limit Exceeded is that this is a loop in your submitted linkedlist.

    class Solution(object):

    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        min_node = ListNode(-1)
        min_node.next = None
        # head.next = None
        node = head
        while node:
            pre = min_node
            root = min_node.next
            while root != None and root.val < node.val:
                pre = root
                root = root.next
                
            pre.next = node
            temp = node.next
            node.next = root
            node = temp
            
        return min_node.next

Log in to reply
 

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