Leetcode 142: Linked List Cycle II - second practice

July 14, 2016

Second practice:

https://gist.github.com/jianminchen/65796a60e7320784231bd1883af0d6f8

Transcript:

 Assuming that you have the knowledge how to find the start node in the cycle. It took 20+ minutes to figure out a solution using simple examples, two simple examples are discussed here:

 http://juliachencoding.blogspot.ca/2016/07/leetcode-142-linked-list-cycle-ii.html

 So, base case coding, line 19 - 20, if the node is null or linked list has only one node, no cycle, return null; 

 Two runners start from start node in the linked list, one moves one step at a time, the fast one moves two steps at a time. 

 Since the fast node explores the linked list in front of the slow one, only check fast node can make 2 steps move or not. 

 The while loop - iteration is to determine if the fast can move forward, if it is true, then slow one can move as well. 

Line 26, while loop, check fast node next two nodes are not empty nodes. 

 Line 27, 28: go to next iteration step, 

 Line 29: check if the slow meets the fast. if it is, find the start node in the cycle:

 Line 29 - 37. The idea is to set slow runner to the start node of linked list, and fast/ slow runners both move one step a time until they meet. 

One concern is the nested while loop from line 29 - 37, the code can be moved out from the while loop, see the practice III:

http://juliachencoding.blogspot.ca/2016/07/leetcode-142-linked-list-cycle-ii-third.html