142. Linked List Cycle II #

Title #

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Problem Summary #

Determine whether the linked list has a cycle，cannot use extra space。If there is a cycle，output the starting pointer of the cycle，if there is no cycle，then output null。

Solution Approach #

This problem is an enhanced version of Problem 141。On the basis of determining whether there is a cycle，it is also necessary to output the first node of the cycle。

Analyze the principle of detecting a cycle。fast pointer moves 2 steps at a time，slow pointer moves 1 step at a time。Let going from linked list head to a point in the cycle require x1 steps，from the first point of the cycle to the meeting point require x2 steps，and from the meeting point in the cycle back to the first point of the cycle require x3 steps。Then the total length of the cycle is x2 + x3 steps。

fast and slow will meet，which shows that the time they walk is the same，so it can be known that the distance they walk has the following relationship：

fast t = (x1 + x2 + x3 + x2) / 2
slow t = (x1 + x2) / 1

x1 + x2 + x3 + x2 = 2 * (x1 + x2)

So x1 = x3

So after the 2 pointers meet，if slow continues to move forward，fast pointer returns to the starting point head，both move one step each time，then they will definitely meet at the starting point of the cycle，after meeting output this point and it is the result。

Code #

package leetcode

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

func hasCycle142(head *ListNode) (bool, *ListNode) {
	fast := head
	slow := head
	for slow != nil && fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			return true, slow
		}
	}
	return false, nil
}