Remove Duplicates From a Linked List

Given the head of an unsorted singly linked list, remove every node whose value already appeared earlier in the list. Keep the first occurrence of each value, in its original position.

Example 1

Text

Input:  7 -> 14 -> 21 -> 14 -> 22 -> 7
Output: 7 -> 14 -> 21 -> 22

graph LR
    A["7"] --> B["14"] --> C["21"] --> D["14 (dup)"] --> E["22"] --> F["7 (dup)"]
    C -. "new link" .-> E
    style D stroke-dasharray: 5 5
    style F stroke-dasharray: 5 5

Example 2

Text

Input:  1 -> 1 -> 1
Output: 1

Brute force: for each node, delete its later copies

Walk an outer node through the list. For each one, walk an inner pointer over the nodes after it, and unlink every node that has the same value as outer. Unlinking means setting prev.next = prev.next.next, where prev is the node right before the copy.

When outer reaches a node, every value before it has already had its later copies removed, so each value that remains appears only once before outer.

A list node here is an object with a mutable next field, and null marks the end of the list.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode removeDuplicates(ListNode head) {
        for (ListNode outer = head; outer != null; outer = outer.next) {
            ListNode prev = outer;
            while (prev.next != null) {
                if (prev.next.val == outer.val) {
                    prev.next = prev.next.next; // unlink the copy
                } else {
                    prev = prev.next;
                }
            }
        }
        return head;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(removeDuplicates(fromArray(7, 14, 21, 14, 22, 7))));
        System.out.println(show(removeDuplicates(fromArray(1, 1, 1))));
    }
}

Output

[7, 14, 21, 22]
[1]

Time: O(n²). Space: O(1). Use this when memory is the constraint.

The head is never removed, because it is the first occurrence of its value, so the method can return head unchanged.

Optimal: one pass with a `HashSet`

Keep a set of the values seen so far, and walk a prev pointer through the list. A HashSet stores each value once, and add returns true only when the value was not already in the set.

If seen.add(val) returns true, the value is new: keep the node and move prev forward.
If it returns false, the value was already there: unlink the node with prev.next = prev.next.next and don't move prev, because prev.next is now the next node, which still has to be checked.

The head is always a first occurrence, so its value goes into the set before the loop.

Walkthrough with 7 -> 14 -> 21 -> 14 -> 22 -> 7:

node	`seen` before	new?	action
7	{}	yes	keep
14	{7}	yes	keep
21	{7, 14}	yes	keep
14	{7, 14, 21}	no	unlink
22	{7, 14, 21}	yes	keep
7	{7, 14, 21, 22}	no	unlink

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode removeDuplicates(ListNode head) {
        if (head == null) return null;
        Set<Integer> seen = new HashSet<>();
        seen.add(head.val);
        ListNode prev = head;
        while (prev.next != null) {
            if (seen.add(prev.next.val)) {
                prev = prev.next;           // new value: keep it
            } else {
                prev.next = prev.next.next; // repeat: unlink it
            }
        }
        return head;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(removeDuplicates(fromArray(7, 14, 21, 14, 22, 7))));
        System.out.println(show(removeDuplicates(fromArray(1, 1, 1))));
        System.out.println(show(removeDuplicates(null)));
    }
}

Output

[7, 14, 21, 22]
[1]
[]

Time: O(n) on average (HashSet operations are O(1) on average). Space: O(n) for the set.

Variant: sorted list (LeetCode 83)

In a sorted list (LeetCode 83), duplicates are next to each other, so comparing each node with its next is enough, and no set is needed:

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val == cur.val) {
                cur.next = cur.next.next; // skip the duplicate
            }
            cur = cur.next;
        }
        return head;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(deleteDuplicates(fromArray(1, 1, 2, 3, 3, 3))));
    }
}

Output

[1, 2, 3]

Time: O(n). Space: O(1).

Edge cases

Empty list or one node: returned unchanged.
All values equal: only the head remains.
No duplicates: the list is unchanged.

Brute force: for each node, delete its later copies

Optimal: one pass with a HashSet

Variant: sorted list (LeetCode 83)

Edge cases

Optimal: one pass with a `HashSet`