My O(1) space and O(n) time python AC code

  • 1

    First using two pointers and to find the steps that the two pointer meet nSteps. nSteps must be a multiple of the number of elements in the cycle nCycle. Second from the node meet that two pointers meet, one can calculate the number of elements in the nCycle. Change the head by nCycle steps does not change the position that two pointers meet. So, we make the new head by deleting the first nPre=nSteps-nCycle steps which is a waste in determining the node that the cycle begins.
    Then iterating simultaneously from meet and the new head will give us the result when two pointers meet again.

    class Solution:
        # @param head, a ListNode
        # @return a list node
        def detectCycle(self, head):
            if not head or not
                return None
            nMeet = 1
            slow, fast = head,
            while slow != fast:
                if and
                    fast =
                    return None
                slow =
                nMeet += 1
            meet, nCycle = slow, 1
            if == head:
                return head
            while != meet:
                slow =
                nCycle += 1
            nPre = nMeet - nCycle
            node, slow = head,
            if nPre != 0:
                for i in xrange(nPre):
                    node =
            while node != slow:
                node, slow =,
            return node

Log in to reply

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