142.Linked_List_Cycle_II.md

142. Linked List Cycle II

Tip. Solution this problem must know 141. first

reference

Floyd's cycle-finding algorithm (also known as the "tortoise and hare" algorithm).

When slow meet fast in cycle, The node passed by slow is x + y, The fast passed node is x + y + n(y+z), n is the number of fast traverse numbers in the cycle, because total passed node is fast = slow*2.

Let :  
    2(x + y) = x + y + n(y + z)  
    x + y = n(y + z)  
    x = n(y + z) - y  
    x = (n - 1)(y + z) + z  
if : 
    n = 1
    x = z

So now we can set a new pointer at first time fast and slow meet node, and traverse linkedlist again. This time slow start from the starting point, new pointer start form meet node, each time moves 1 node. Because x = z, So when slow and new point meet, this node is the cycle start node.

In this algorithm part 1 time complexity is O(n), In part 2 is also O(n) it the worst case. Therefore, the overall time complexity of the function is O(n).

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	virtualhead := &ListNode{Next: head}
	slow := virtualhead
	fast := virtualhead
	for slow != nil && fast.Next != nil && fast.Next.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
		if slow == fast {
			slow := virtualhead
			meet := fast
			for slow != meet {
				slow = slow.Next
				meet = meet.Next
			}
			return slow
		}
	}
	return nil
}