First using two pointers
slow=slow.next to find the steps that the two pointer meet
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
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