Deletion from a circular linked list

Easy

Problem

Delete the node with a given value from a circular linked list. Handle the special cases: deleting the head, deleting the only node, and a value that is not present.

Example 1

Input:  2 → 5 → 7 → 8 → 10 → (2), delete 5
Output: 2 → 7 → 8 → 10 → (2)

Also asked as: Deletion from a Circular Linked List

Test cases

Case 1

Input:    [2,5,7,8,10], 5
Expected: [2,7,8,10]

Case 2

Input:    [2,5,7], 2
Expected: [5,7]

Case 3

Input:    [1,2,3], 9
Expected: [1,2,3]

Case 4

Input:    [4], 4
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Find the node, relink its predecessor

Time O(n)Space O(1)

Walk from head until the next node holds the target value; point current.next past it. If the deleted node is the head, update head (and the last node's next). Handle the single-node case.

function deleteFromCircular(head, key) {
if (!head) return null;
if (head.val === key && head.next === head) return null; // only node
let last = head;
while (last.next !== head) last = last.next; // node before head
if (head.val === key) { last.next = head.next; return head.next; }
let cur = head;
while (cur.next !== head && cur.next.val !== key) cur = cur.next;
if (cur.next.val === key) cur.next = cur.next.next;
return head;
}