Easy Lists
Remove Duplicates (Singly Linked List)
Receives an array of integers and builds a singly linked list, where each node holds a value and a next pointer to the following node. It walks the list from head to tail using a set to track seen values; the first occurrence of each value is kept and any later duplicate node is unlinked by redirecting its predecessor's next pointer. Returns the head of the filtered list with each value appearing exactly once, preserving the original order.
Visualization
- Input
- Result
Algorithm code
/**
* @typedef {{ value: number, next: SLLNode | null }} SLLNode
*/
/**
* @param {number[]} arr
* @returns {SLLNode | null} head of the deduplicated singly linked list
*/
export function removeDuplicatesSLL(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;
}
const seen = new Set([head.value]);
let prev = head;
let node = head.next;
while (node !== null) {
const next = node.next;
if (seen.has(node.value)) {
prev.next = next;
} else {
seen.add(node.value);
prev = node;
}
node = next;
}
return head;
}FUNCTION removeDuplicatesSLL(arr):
IF arr is empty: RETURN null
// Build the singly linked list
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
// Remove duplicates using a seen-set
seen ← { head.value }
prev ← head
node ← head.next
WHILE node ≠ null:
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