Medium Lists
Remove Duplicates (Circular Linked List)
Receives an array of integers and builds a circular linked list, where each node holds a value and a next pointer — and the last node's next points back to the head instead of null. It walks the list starting from head's successor using a while loop that stops when it reaches head again, tracking seen values with a set; the first occurrence of each value is kept and any duplicate node is unlinked by redirecting its predecessor's next. Returns the head of the filtered circular list with each value appearing exactly once, preserving the original order.
Visualization
- Input
- Result
Algorithm code
/**
* @typedef {{ value: number, next: CLLNode }} CLLNode
*/
/**
* @param {number[]} arr
* @returns {CLLNode | null} head of the deduplicated circular linked list
*/
export function removeDuplicatesCLL(arr) {
if (arr.length === 0) return null;
let head = { value: arr[0], next: null };
let cur = head;
for (let i = 1; i < arr.length; i++) {
cur.next = { value: arr[i], next: null };
cur = cur.next;
}
cur.next = head;
const seen = new Set([head.value]);
let prev = head;
let node = head.next;
while (node !== head) {
const next = node.next;
if (seen.has(node.value)) {
prev.next = next;
} else {
seen.add(node.value);
prev = node;
}
node = next;
}
return head;
}FUNCTION removeDuplicatesCLL(arr):
IF arr is empty: RETURN null
// Build the circular linked list (last node points back to head)
head ← Node(arr[0], next: null)
cur ← head
FOR i FROM 1 TO length(arr) - 1:
cur.next ← Node(arr[i], next: null)
cur ← cur.next
cur.next ← head // close the circle
// Remove duplicates using a seen-set (stop when we reach head again)
seen ← { head.value }
prev ← head
node ← head.next
WHILE node ≠ head:
next ← node.next
IF node.value IN seen:
prev.next ← next // skip duplicate
ELSE:
ADD node.value TO seen
prev ← node
node ← next
RETURN head