Remove repeated keys from a sorted Java linked chain

Last updated: 1 Oct 20264 min read

tutorial

Deduplicating a sorted linked chain can keep the first node for each key by bypassing adjacent nodes with equal keys.

Use the ordering precondition

Equal keys must be adjacent. Compare each node with its successor; when keys match, bypass the successor and clear that removed node's next reference. Keep the cursor on the retained node because a run may contain more than two copies. Advance only after the next key differs.

This policy keeps the first record of a duplicate run. If the product instead requires the latest record or rejects all duplicates, the algorithm and its output contract must change. The linked chain itself does not enforce sorted order.

Separate keys from node identity

The fixture uses numeric shipment keys rather than comparing Node references. Two records with key 47 are distinct nodes, but one is removed under this value-based policy. Intersection detection asks a different question: whether two paths reach the same object.

If input order is uncertain, sort first with linked merge sort or use a set with its corresponding memory cost. A single adjacent comparison is insufficient on unsorted input.

Working program

public class SortedShipmentDeduplication {
    static final class Node {
        final int shipmentKey;
        Node next;
        Node(int shipmentKey, Node next) { this.shipmentKey = shipmentKey; this.next = next; }
    }
    static Node keepFirstPerKey(Node head) {
        for (Node cursor = head; cursor != null && cursor.next != null;) {
            if (cursor.shipmentKey == cursor.next.shipmentKey) {
                Node removed = cursor.next;
                cursor.next = removed.next;
                removed.next = null;
            } else cursor = cursor.next;
        }
        return head;
    }
    static String keys(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.shipmentKey);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node(15, new Node(15, new Node(47,
            new Node(47, new Node(47, new Node(82, null))))));
        System.out.println(keys(keepFirstPerKey(head)));
        System.out.println(keepFirstPerKey(null) == null);
    }
}

Output

15,47,82
true

Cost and ownership

One pass costs O(n) time and O(1) extra references. The operation mutates the original chain and retains the first Node object of each equal-key run; it does not copy records.

Common Mistakes

Do not apply adjacent deduplication to unsorted input.
Do not advance the cursor immediately after removing one duplicate; a run may continue.
Do not equate duplicate key values with shared Node identity.