LeetCode142 Linked List Cycle II

Author: Stefan Su
*Create time: *
Location: New York City, NY, USA

Description Medium

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

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.

Constrains

• The number of the nodes in the list is in the range [0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• pos is -1 or a valid index in the linked-list.

Analysis

Two points

1. Check if a linked list is cyclic
2. If there is a ring, how to find the entrance to this ring

Details

1. Check if a linked list is cyclic

   You can use the two pointers method to define the fast and slow pointers respectively. Starting from the head node, the fast pointer moves two nodes at a time, and the slow pointer moves one node at a time. If the fast and slow pointers meet on the way, it means that the linked list has a ring.

   Why do fast go to two nodes and slow go to one node, and if there is a ring, they will definitely meet in the ring instead of being staggered forever?

   First of all, the first point: the fast pointer must enter the ring first. If the fast pointer and the slow pointer meet, they must meet in the ring, which is beyond doubt.

   So let’s see, why the fast pointer and the slow pointer must meet?

   You can draw a ring and let the fast pointer start catching up with the slow pointer at any node.
   fast and slow each take one step further, fast and slow meet

   This is because fast takes two steps and slow takes one step. In fact, compared with slow, fast is a node that is close to slow, so fast must be able to overlap with slow.

2. If there is a ring, how to find the entrance to this ring

   At this point, it can be judged whether the linked list has a ring, so the next step is to find the entry of this ring.

   Suppose the number of nodes from the head node to the ring entry node is x. The number of nodes from the ring entry node to the node where the fast pointer meets the slow pointer is y. The number of nodes from the encounter node to the ring entry node is z. As the picture shows:

   

   Then when they meet: The number of nodes passed by the slow pointer is: x + y, the number of nodes passed by the fast pointer: x + y + n (y + z), where n is the fast pointer after n circles in the ring to meet the slow pointer, (y+z) is the number A of nodes in a circle.

   Because the fast pointer walks two nodes at a time, and the slow pointer walks one node at a time, the number of nodes traversed by the fast pointer equals to twice of the number of nodes traversed by the slow pointer:

   (x + y) * 2 = x + y + n(y + z)

   Eliminate one on both sides (x+y): x + y = n (y + z)

   Because the entrance to the ring is to be found, x is required, because x represents the distance from the head node to the ring entrance node.

   So ask for x, put x alone on the left: x = n (y + z) - y,

   Then come up with a (y+z) from n(y+z). After sorting out the formula, it is the following formula: x = (n - 1) (y + z) + z Note that n must be greater than or equal to 1 here, because the fast pointer needs to travel at least one more circle to meet the slow pointer.

   What does this formula say?

   Let’s take the case where n is 1 as an example, which means that after the fast pointer turns around in the ring, it encounters the slow pointer.

   When n is 1, the formula resolves to x = z,

   This means that a pointer is set from the head node, and a pointer is also set from the encounter node. These two pointers only go one node at a time, so when these two pointers meet, it is the node of the ring entry.

   That is, at the encounter node, define a pointer index1, and set a pointer index2 at the head node.

   Let index1 and index2 move at the same time, one node at a time, then the place where they meet is the node of the ring entrance.

   So what happens if n is greater than 1, that is, the fast pointer encounters the slow pointer after n circles in the ring.

   In fact, this situation is the same as when n is 1, and the entry node of the ring can be found by this method, but the index1 pointer turns (n-1) more times in the ring, and then encounters index2, the meeting point is still the entry node of the ring.

Solution

• Two pointers version

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) {
                ListNode index_1 = fast;
                ListNode index_2 = head;
                while (index_1 != index_2) {
                    index_1 = index_1.next;
                    index_2 = index_2.next;
                }
                return index_1;
            }
        }
        return null;
    }
}

Hopefully, this blog can inspire you when solving LeetCode142. For any questions, please comment below.