grid47 Exploring patterns and algorithms
Oct 23, 2024
5 min read
Solution to LeetCode 141: Linked List Cycle Problem
Given the head of a linked list, determine if there is a cycle. A cycle occurs if a node can be revisited by following the ’next’ pointers. The ‘pos’ parameter denotes where the last node connects to. If ‘pos’ is -1, there is no cycle.
Problem
Approach
Steps
Complexity
Input: The input consists of a linked list head and a position, 'pos', indicating where the tail node connects.
Example: Input: head = [4, 3, 2, 1], 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 a boolean value indicating whether a cycle exists in the linked list.
Example: Output: true
Constraints:
• The output is true if a cycle exists, otherwise false.
Goal: The goal is to detect if there is a cycle in the linked list using efficient memory usage.
Steps:
• 1. Use two pointers, 'slow' and 'fast', where 'slow' moves one step and 'fast' moves two steps at a time.
• 2. If there is a cycle, the two pointers will meet; otherwise, the fast pointer will reach the end of the list.
Goal: The solution should be optimized for both time and space complexity.
Steps:
• Ensure the solution runs efficiently for lists with up to 10^4 nodes.
• The space complexity must be constant, O(1).
Assumptions:
• The linked list can have a cycle, or it can be a simple acyclic list.
• All nodes contain integer values.
• Input: Input: head = [4, 3, 2, 1], pos = 2
• Explanation: In this example, the tail node points to the 2nd node, forming a cycle.
Approach: The approach leverages the Floyd's Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm), using two pointers to detect cycles in constant space.
Observations:
• We need to detect a cycle using minimal space, ideally O(1).
• By using two pointers, one slow and one fast, we can determine if there is a cycle without using additional data structures.
Steps:
• 1. Initialize two pointers, slow and fast, both starting at the head of the list.
• 2. Move the slow pointer one step and the fast pointer two steps at a time.
• 3. If the slow and fast pointers meet, return true (cycle detected).
• 4. If the fast pointer reaches the end of the list (nullptr), return false (no cycle).
Empty Inputs:
• An empty list should return false since no cycle can exist.
Large Inputs:
• For large lists, the solution should efficiently detect cycles without using extra memory.
Special Values:
• When the cycle starts at the very first node or is self-referential (the last node points to itself).
Constraints:
• Ensure constant space usage (O(1)) and linear time complexity (O(n)) for large inputs.
This is the definition of the `hasCycle` function, which takes a pointer `head` to the first node of a linked list and returns a boolean indicating whether the list contains a cycle.
2 : Pointer Initialization
ListNode* slow = head, *fast = head;
Two pointers, `slow` and `fast`, are initialized to point to the head of the linked list. The `slow` pointer will move one step at a time, while the `fast` pointer will move two steps at a time.
3 : While Loop (Cycle Detection)
while(fast && fast->next) {
The while loop continues as long as the `fast` pointer and its next node are not `nullptr`. This ensures that the loop doesn't run into an invalid memory reference when traversing the list.
4 : Move Slow Pointer
slow = slow->next;
The `slow` pointer moves one step forward in the list, advancing by one node at a time.
5 : Move Fast Pointer
fast = fast->next->next;
The `fast` pointer moves two steps forward, advancing by two nodes at a time.
6 : Cycle Detection
if(slow == fast) returntrue;
If the `slow` pointer and `fast` pointer meet at the same node, it indicates that a cycle exists in the linked list. The function returns `true`.
7 : Return False (No Cycle)
returnfalse;
If the `fast` pointer reaches the end of the list (i.e., `fast` or `fast->next` becomes `nullptr`), no cycle is present, so the function returns `false`.
Best Case: O(n), where n is the number of nodes in the list. The best case occurs when there is no cycle, and the fast pointer reaches the end of the list.
Average Case: O(n), the fast and slow pointers will eventually meet if there is a cycle.
Worst Case: O(n), the worst case is when there is no cycle, and the fast pointer needs to traverse the entire list.
Description: The time complexity is O(n) since each pointer traverses the list at most once.
Best Case: O(1), regardless of whether the list has a cycle or not, only two pointers are maintained.
Worst Case: O(1), the space complexity is constant since only two pointers are used.
Description: The space complexity is O(1), as we are not using any additional data structures.
