Delete the loop in a linked list
Problem
The list may contain a cycle. Find the node where the cycle starts and break the loop by setting the last node's next to null, leaving a plain list.
Example 1
Input: 1 → 3 → 4 → (back to 3) Output: 1 → 3 → 4 → null
The cycle starts at node 3.
Also asked as: Write a program to Delete loop in a linked list · Find the starting point of the loop
Test cases
Case 1
Input: [[1,3,4],1] Expected: [1,3,4]
Case 2
Input: [[1,2,3,4],0] Expected: [1,2,3,4]
Case 3
Input: [[1,2],-1] Expected: [1,2]
View solutionHide solution1 approach
1. Floyd — find the entry, then break it
Time O(n)Space O(1)
After tortoise/hare meet, move one pointer to head; advance both by 1 until they meet again — that node is the loop start. Walk to the node whose next is the start and null it.
function detectAndRemoveLoop(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) break; } if (!fast || !fast.next) return head; // no loop slow = head; if (slow === fast) { while (fast.next !== slow) fast = fast.next; } else { while (slow.next !== fast.next) { slow = slow.next; fast = fast.next; } } fast.next = null; return head;}