This problem is frequently asked in coding interviews and will enhance the LinkedList folder with an important cycle-handling algorithm.
Details
Approach:
Use two pointers (slow and fast) to detect a cycle.
If they meet, a loop exists.
To remove the loop, find the starting node of the cycle and set the previous node’s next pointer to null.
Input Example:
1 → 2 → 3 → 4 → 5
↑ ↓
8 ← 6
Output Example:
1 → 2 → 3 → 4 → 5 → 6 → 8
(Loop removed, list becomes linear).
Complexity:
Time: O(n)
Space: O(1) (no extra space used).
File to Add
LinkedList/DetectAndRemoveLoop.java
This problem is frequently asked in coding interviews and will enhance the LinkedList folder with an important cycle-handling algorithm.
Details
Approach:
Use two pointers (slow and fast) to detect a cycle.
If they meet, a loop exists.
To remove the loop, find the starting node of the cycle and set the previous node’s next pointer to null.
Input Example:
1 → 2 → 3 → 4 → 5
↑ ↓
8 ← 6
Output Example:
1 → 2 → 3 → 4 → 5 → 6 → 8
(Loop removed, list becomes linear).
Complexity:
Time: O(n)
Space: O(1) (no extra space used).
File to Add
LinkedList/DetectAndRemoveLoop.java