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


  • 1
    Z

    First using two pointers fast=fast.next.next and slow=slow.next 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 head.next:
                return None
            nMeet = 1
            slow, fast = head, head.next
            while slow != fast:
                if fast.next and fast.next.next:
                    fast = fast.next.next
                else:
                    return None
                slow = slow.next
                nMeet += 1
            meet, nCycle = slow, 1
            if meet.next == head:
                return head
            while slow.next != meet:
                slow = slow.next
                nCycle += 1
            nPre = nMeet - nCycle
            node, slow = head, meet.next
            if nPre != 0:
                for i in xrange(nPre):
                    node = node.next
            while node != slow:
                node, slow = node.next, slow.next
            return node

Log in to reply
 

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