I always get TLE at {1, 1}, but how can I solve it?


  • 0
    V
    class Solution:
    def insertionSortList(self, head):
        ans = None
        cur = head
        tmp = ListNode(0)
        while cur is not None:
            if ans is None or ans.val > cur.val:
                tmp.val = cur.val
                tmp.next = ans
                ans = tmp
                cur = cur.next
                continue
            ptr = ans
            while ptr.next is not None and cur.val >= ptr.next.val:
                ptr = ptr.next
            tmp.val = cur.val
            tmp.next = ptr.next
            ptr.next = tmp
            cur = cur.next
        return ans
    

    I debugged for a few time and found that aftertmp.next = ptr.next they will point to the same object, and then ptr.next = tmp will make tmp.next point to tmp itself. But why? How can I solve it?


  • 0
    T

    if not inserted in the middle of the already sorted sequence , your ptr and tmp pointer point to the same node. solution is when this condition happens , do not insert , move to next node


Log in to reply
 

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