Leetcode 142: Linked List Cycle II - two examples to show the idea

July 14, 2016

 Work on facebook code lab - Linked List Cycle, same question as Leetcode 142.

 Problem statement:

 Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Work on two simple examples, and then, figure out the solution first:

Example 1: 

Example 2:

First, find the node two pointers meets - one slow runner, one step a time; one fast runner, two steps a time. If there is a cycle, two nodes will meet. 

And then, start from meeting place, one node starts from node 0, slow node continues from meeting place, then, two nodes will meet at the beginning of cycle. 

Facts about the practice: 

1. Julia worked on this problem before. But she has to figure out the solution again. 

2. Spent over 20+ minutes and still confused about the solution. 

two distance values: 

meeting place -> cycle starting node

cycle starting node -> meeting place
Use the first one, not second one. But, Julia was trying to figure out the second one. 

Denote d1 as starting node to cycle starting node
Denote d2 as cycle length

Discuss two cases:
d1 > d2,
d1 <= d2,
and when the two pointers meet, the fast node may go through cycle more than once.

The formula is not deterministic, so it is better to go through the simple example, and then, make a guess.

3. Google the blog about the solution:
https://siddontang.gitbooks.io/leetcode-solution/content/linked_list/linked_list_cycle.html

July 15, 2016

Read more blogs:

The analysis has some issues: 

http://www.cnblogs.com/hiddenfox/p/3408931.html
http://www.cnblogs.com/wuyuegb2312/p/3183214.html

http://yucoding.blogspot.ca/2013/12/leetcode-question-linked-list-cycle-ii.html