Question Name: Linked List Cycle II
Same as the problem in Cracking the Coding Interview.
Solution to Linked List Cycle II by LeetCode
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# @param head, a ListNode
# @return a boolean
def detectCycle(self, head):
if head == None: return None
slower = head # Move one step each time
quicker = head # Move two steps each time
while quicker.next != None and quicker.next.next != None:
slower = slower.next
quicker = quicker.next.next
# The slower and quicker meet with each other. There is a cycle.
if slower == quicker: break
# quicker reach the end. Limited list never have cycle.
# Both latter and former move one step in each round, until they meet.
# The meeting place is the entry point of cycle.
latter, former = head, quicker
while latter != former:
latter = latter.next
former = former.next