Write a program to Delete loop in a linked list
Delete Loop in a Linked List
Problem Statement
Given the head of a linked list that may contain a cycle, remove the cycle if present and return the head of the linked list. The linked list should be modified in-place without using extra space.
Example
Input: head = [1, 2, 3, 4, 5], pos = 2 (5 connects back to node 3)
Before: 1 -> 2 -> 3 -> 4 -> 5
↑ |
|_________|
After: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: [1, 2, 3, 4, 5]
Input: head = [1, 2], pos = 0 (2 connects back to 1)
Before: 1 -> 2
↑ |
|____|
After: 1 -> 2 -> null
Output: [1, 2]
Brute Force Approach (Using HashSet)
Intuition
We can use a hash set to track visited nodes. When we find a node whose next pointer points to an already visited node, we've found the last node before the cycle starts. We simply set its next to null to break the cycle.
Algorithm
- Create a hash set to store visited nodes
- Traverse the linked list with two pointers: prev and curr
- For each node:
- If curr is in the set, prev.next = null (break the cycle)
- Otherwise, add curr to the set
- Continue until cycle is broken or end is reached
Implementation
Complexity Analysis
- Time Complexity: O(n) - Each node is visited at most once
- Space Complexity: O(n) - Hash set stores all nodes
Optimal Approach (Floyd's Algorithm)
Intuition
We use Floyd's cycle detection to find where the slow and fast pointers meet. Then, we find the start of the cycle and the node just before it to break the loop.
Key insight: After detecting the cycle, if we reset one pointer to head and move both at the same speed, they will meet at the start of the cycle.
Algorithm
- Detect cycle using Floyd's algorithm (slow and fast pointers)
- If no cycle, return head
- Find the start of the cycle:
- Reset slow to head
- Move both slow and fast one step at a time
- They meet at the cycle start
- Find the last node in the cycle (node whose next is cycle start)
- Set that node's next to null
Visualization
List: 1 -> 2 -> 3 -> 4 -> 5
↑ |
|_________|
Step 1: Detect cycle
- slow and fast meet at some point in cycle
Step 2: Find cycle start
- Reset slow to head
- Move both one step at a time
- They meet at node 3 (cycle start)
Step 3: Find last node in cycle
- Start from cycle start (3)
- Move until next node is cycle start
- Last node is 5
Step 4: Break the cycle
- Set node 5's next to null
Result: 1 -> 2 -> 3 -> 4 -> 5 -> null
Implementation
Complexity Analysis
- Time Complexity: O(n) - Each phase visits nodes at most once
- Space Complexity: O(1) - Only using constant extra space
Alternative Approach: Count Cycle Length
Another way to solve this is:
- Detect cycle and find meeting point
- Count the cycle length (k) by traversing the cycle once
- Use two pointers: advance one by k steps, then move both until they meet at cycle start
- Find the node before cycle start and break the loop
Implementation
Key Takeaways
- This problem combines cycle detection with finding the cycle start
- The special case when the cycle starts at head must be handled separately
- We need to find the last node in the cycle (whose next is cycle start) to break it
- Floyd's algorithm gives us O(1) space complexity
- Understanding the mathematical proof of why pointers meet at cycle start is important
- This is a follow-up to the basic cycle detection problem