Remove Duplicates From a Linked List (Hashing)

Given the head of an unsorted singly linked list, remove every node whose value appeared earlier in the list. The first occurrence of each value stays in place.

This is the hashing version of Remove Duplicates From a Linked List.

Example

Text

Input:  1 -> 2 -> 1 -> 3 -> 2 -> 4
Output: 1 -> 2 -> 3 -> 4

graph LR
    A["1"] --> B["2"] --> C["1 (dup)"] --> D["3"] --> E["2 (dup)"] --> F["4"]
    B -. "new link" .-> D
    D -. "new link" .-> F
    style C stroke-dasharray: 5 5
    style E stroke-dasharray: 5 5

Brute force: for each node, remove its later copies

Linked structures in Java use null for "no next node" and mutable next fields, so no wrapper types are needed. Walk an outer node through the list. For each one, run an inner pointer over the nodes after it and unlink every node with the same value. Unlinking means setting the previous node's next to the node after the duplicate.

Java

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

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

    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 toText(ListNode head) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = head; n != null; n = n.next) {
            if (n != head) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    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 duplicate
                } else {
                    prev = prev.next;
                }
            }
        }
        return head;
    }

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

Output

[1, 2, 3, 4]

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

Optimal: one pass with a HashSet

Keep a prev pointer to the last kept node. seen.add(val) returns true for a new value: keep the node and move prev to it. It returns false for a repeated value: unlink the node with prev.next = prev.next.next, and stay on the same prev, whose next is now the following node. The head is always kept, so prev starts there.

Walkthrough:

node	`seen` before	`add` returns	action
1	{}	true	keep
2	{1}	true	keep
1	{1, 2}	false	unlink
3	{1, 2}	true	keep
2	{1, 2, 3}	false	unlink
4	{1, 2, 3}	true	keep

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 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 toText(ListNode head) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = head; n != null; n = n.next) {
            if (n != head) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    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;
            } else {
                prev.next = prev.next.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        System.out.println(toText(removeDuplicates(fromArray(1, 2, 1, 3, 2, 4))));
        System.out.println(toText(removeDuplicates(fromArray(5, 5, 5))));
        System.out.println(toText(removeDuplicates(fromArray())));
    }
}

Output

[1, 2, 3, 4]
[5]
[]

Time: O(n). Space: O(n) for the set.

prev.next = prev.next.next replaces the duplicate node with everything after it. Nothing refers to the removed node afterwards, so the garbage collector reclaims it.