Question: https://oj.leetcode.com/problems/linked-list-cycle-ii/
Question Name: Linked List Cycle II
Same as the problem in Cracking the Coding Interview.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | # 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 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 else: # quicker reach the end. Limited list never have cycle. return None # 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 return former |