Linked List Cycle II - LeetCode

Can you solve this real interview question? Linked List Cycle II - 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: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png] 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: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png] 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: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png] Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.   Constraints: * The number of the nodes in the list is in the range [0, 104]. * -105 <= Node.val <= 105 * pos is -1 or a valid index in the linked-list.   Follow up: Can you solve it using O(1) (i.e. constant) memory?

https://leetcode.com/problems/linked-list-cycle-ii/description/

Detecting the Start of a Cycle in a Linked List

Understanding the Solution with Two Pointers

Step 1: Initialize Slow and Fast Pointers

• We start with two pointers: slow and fast, both initially pointing to the head of the linked list.

• The slow pointer moves one step at a time (slow = slow->next).

• The fast pointer moves two steps at a time (fast = fast->next->next).

Step 2: Detecting the Cycle

• We move both pointers in their respective steps until they either meet or reach the end of the list.

• If there is a cycle, the fast pointer will eventually "catch up" to the slow pointer inside the cycle. This is similar to a faster runner on a circular track eventually catching up with a slower runner.

• If there is no cycle, the fast pointer will reach the end (null), and we can return null indicating no cycle is present.

Step 3: Finding the Entry Point of the Cycle

• Once we detect the cycle (i.e., slow and fast meet), we need to determine the start of the cycle.

• To find the entry point, we initialize another pointer, entry, at the head of the linked list.

• We then move both the entry and slow pointers one step at a time until they meet. The point at which they meet is the start of the cycle.

Why Does This Work?

1. Meeting Point Logic:
• Suppose the linked list is divided into two parts:
• The distance from the head to the start of the cycle is a.
• The distance from the start of the cycle to the meeting point is b.
• The remainder of the cycle (back to the start of the cycle) is c.
• When the slow pointer and fast pointer meet, the distance covered by the fast pointer is twice that of the slow pointer:
• fast = 2 * slow.
• If we denote the total distance traveled by the slow pointer as a + b, then the fast pointer travels a + b + b + c = 2(a + b).
• Simplifying this, we get: a = c.

2. Finding the Entry Point:
• After detecting the cycle, if we move a new pointer entry from the head and move the slow pointer from the meeting point, both will meet at the start of the cycle after a steps.
• This is because the distance from the head to the start of the cycle is equal to the distance from the meeting point to the start of the cycle (a = c).

Code Implementation in C

Complexity Analysis

• Time Complexity: O(n)
• In the worst case, we traverse each node at most twice—once to detect the cycle and once to find the start of the cycle. Therefore, the time complexity is linear in terms of the number of nodes.

• Space Complexity: O(1)
• This algorithm uses a constant amount of extra space, as we only need a few pointer variables.