Delete the loop in a linked list

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}