O(n) time complexity and O(1) time complexity for the problem but got TLE[Python]


  • 0
    L

    A simple method by break the original list. We scan the list once and cur.next = cur to beak it,if there is a cycle we will back to a front node again for which the cur.next == cur test returns True.
    BUT my solution got TLE for the simple test case [3,2,0,-4] tail points to index 1.
    Anyone can find the problem?

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param head, a ListNode
        # @return a list node
        def detectCycle(self, head):
            if not head:
                return None
            if head.next == head:
                return head
            cur = head
            while cur:
                if cur.next == cur:
                    return cur
                temp = cur.next
                cur.next = cur
                cur = temp
                
            return None

Log in to reply
 

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