grid47 Exploring patterns and algorithms
Oct 23, 2024
6 min read
Solution to LeetCode 142: Linked List Cycle II Problem
Given the head of a linked list, find the node where the cycle begins. If no cycle exists, return null. The list may contain a cycle, which occurs if a node can be revisited by following the ’next’ pointers continuously.
Problem
Approach
Steps
Complexity
Input: The input consists of a linked list and an index 'pos' where the tail node connects. If 'pos' is -1, there is no cycle.
Example: Input: head = [5, 3, 9, 4], pos = 2
Constraints:
• The number of nodes in the list is between 0 and 10^4.
• Node values range between -10^5 and 10^5.
• 'pos' is either -1 or a valid index within the list.
Output: The output is the node where the cycle begins, or null if no cycle is detected.
Example: Output: tail connects to node index 2
Constraints:
• The output is the node where the cycle begins, or null if no cycle exists.
Goal: The goal is to detect the node where the cycle begins in the linked list.
Steps:
• 1. Use two pointers, 'slow' and 'fast', which start at the head of the list.
• 2. Move the slow pointer one step and the fast pointer two steps at a time.
• 3. If a cycle exists, slow and fast pointers will meet at some point.
• 4. Once a cycle is detected, reset one pointer to the head and keep the other at the meeting point.
• 5. Move both pointers one step at a time until they meet again. This is the start of the cycle.
Goal: The solution should efficiently detect the cycle and identify the starting node without modifying the linked list.
Steps:
• The solution should run in linear time, O(n), and use constant space, O(1).
Assumptions:
• The linked list may contain a cycle or it may be acyclic.
• Nodes may contain integer values.
• Input: Input: head = [5, 3, 9, 4], pos = 2
• Explanation: In this example, the linked list has a cycle where the tail connects to the 2nd node (index 2).
Approach: The solution uses Floyd's Cycle-Finding Algorithm (Tortoise and Hare) to detect the cycle and then find the starting node of the cycle.
Observations:
• The problem can be solved by detecting the cycle first and then finding the cycle's start node.
• By using two pointers, one moving faster than the other, we can detect the cycle in O(n) time. Once the cycle is detected, finding the start node requires another O(n) pass.
Steps:
• 1. Initialize two pointers, slow and fast, both pointing to the head of the list.
• 2. Move the slow pointer one step and the fast pointer two steps at a time.
• 3. If the fast pointer reaches the end (nullptr), return null (no cycle).
• 4. If slow and fast pointers meet, a cycle exists.
• 5. Reset one pointer to the head and keep the other at the meeting point. Move both pointers one step at a time until they meet again, which is the start of the cycle.
Empty Inputs:
• An empty linked list should return null since there is no cycle.
Large Inputs:
• The algorithm should efficiently handle large lists with up to 10^4 nodes.
Special Values:
• When the cycle begins at the very first node or is self-referential (the last node points to itself).
Constraints:
• The solution should run in linear time (O(n)) and use constant space (O(1)).
This defines the `detectCycle` function that takes a pointer `head` to the start of the linked list and returns a pointer to the node where the cycle begins, or `NULL` if no cycle exists.
2 : Base Case Check
if(head ==NULL) returnNULL;
If the list is empty (i.e., `head` is `NULL`), the function immediately returns `NULL`, as there can be no cycle in an empty list.
3 : Pointer Initialization
ListNode *fast = head, *slow= head;
Two pointers, `fast` and `slow`, are initialized to the head of the linked list. `fast` moves two steps at a time and `slow` moves one step at a time.
4 : Cycle Detection Loop
while(fast && fast->next) {
This loop continues as long as `fast` and `fast->next` are valid, ensuring we do not run into null references while traversing the list.
5 : Move Slow Pointer
slow = slow->next;
The `slow` pointer moves one step forward in the linked list.
6 : Move Fast Pointer
fast = fast->next->next;
The `fast` pointer moves two steps forward in the list.
7 : Cycle Detection Check
if(fast == slow) break;
If the `fast` and `slow` pointers meet at the same node, a cycle is detected, and the loop breaks.
8 : No Cycle Check
if(!(fast && fast->next)) returnNULL;
If the `fast` pointer reaches the end of the list (`fast` or `fast->next` is `NULL`), no cycle exists, and the function returns `NULL`.
9 : Second Loop for Cycle Start
while (head != slow) {
This loop moves both `head` and `slow` pointers one step at a time to find the node where the cycle begins.
10 : Move Head Pointer
head = head->next;
Moves the `head` pointer one step forward.
11 : Move Slow Pointer
slow = slow->next;
Moves the `slow` pointer one step forward.
12 : Return Cycle Start Node
return slow;
At this point, both the `head` and `slow` pointers are at the node where the cycle starts, and this node is returned.
Best Case: O(n), when the cycle is detected after moving through most of the list.
Average Case: O(n), the slow and fast pointers will meet at some point if a cycle exists.
Worst Case: O(n), in the worst case, the fast pointer will traverse the entire list.
Description: The time complexity is O(n) because each pointer moves at most n steps.
Best Case: O(1), since no extra space is used.
Worst Case: O(1), as the solution only uses two pointers.
Description: The space complexity is O(1), as only two pointers are used for cycle detection.
