Remove Duplicates in a Un-sorted Linked List

The problem, simply

You get a linked list whose numbers are in no special order, like 4 -> 2 -> 4 -> 1 -> 2. Some numbers appear more than once, and the copies can be far apart.

Keep the first box of each number and remove every later copy. The boxes you keep must stay in their old order. Give back the head.

A story to remember it

Picture it

Examples

Way 1: the simple way

No guest book. For each box you keep, walk the rest of the chain and remove every box with the same number.

1. outer walks the chain one box at a time.
2. For each outer, a second finger inner starts at outer and looks at inner.next.
3. If inner.next has the same number as outer, skip it with inner.next = inner.next.next. Otherwise move inner forward.

class Solution {
    public ListNode removeDuplicates(ListNode head) {
        for (ListNode outer = head; outer != null; outer = outer.next) {
            ListNode inner = outer;
            while (inner.next != null) {
                if (inner.next.val == outer.val) {
                    inner.next = inner.next.next;   // remove a later copy
                } else {
                    inner = inner.next;
                }
            }
        }
        return head;
    }
}

How long it takes: for each box, a walk over the rest of the chain, so about n * n / 2 steps, O(n^2). Extra room: two fingers, O(1). Good to mention when memory is very tight.

Way 2: the clever way

Use the guest book: a bag of numbers seen so far, a hash set. Checking the bag takes about one step, no matter how big it is.

1. prev is the last box we kept. It starts as null.
2. curr walks the chain.
3. If curr.val is already in the bag, unhook curr by setting prev.next = curr.next. prev stays where it is.
4. Otherwise put curr.val in the bag, and move prev to curr.

import java.util.*;

class Solution {
    public ListNode removeDuplicates(ListNode head) {
        Set<Integer> seen = new HashSet<>();   // the guest book
        ListNode prev = null;
        for (ListNode curr = head; curr != null; curr = curr.next) {
            if (seen.contains(curr.val)) {
                prev.next = curr.next;         // send the copy home, prev stays
            } else {
                seen.add(curr.val);
                prev = curr;                   // a keeper
            }
        }
        return head;
    }
}

prev is never null when we find a copy, because the head is always new. How long it takes: one walk, and each bag check is about one step, O(n). Extra room: the bag can hold every distinct number, O(n).

Watch out for

• Do not sort first if the order must be kept. Sorting then removing neighbors gives the right numbers in the wrong order.
• seen.add returns false when the number is already there. You can use if (!seen.add(curr.val)) as a shorter test.
• Very large numbers or objects in the boxes: the bag still works, but its keys must have a good hashCode and equals.

What interviewers ask next

• No extra room allowed? Use Way 1, O(n^2) time and O(1) room. Or, if order may change, sort with merge sort (O(n log n)) and then remove neighbor copies.
• Remove every number that appears more than once, keeping none of them? Count with a map in a first walk, then in a second walk unhook every box whose count is above 1. Use a dummy box in front, since the head may go.
• The chain is huge and the numbers are small, say 0 to 1000. Use a boolean array of size 1001 instead of a hash set. It is faster and needs fixed room.
• What if two copies must stay, not one? Store a count instead of a yes or no, and unhook a box when its count would go past 2.

Remember this

Grown-up words: the guest book is a hash set, the boxes are nodes, unhooking is changing the next pointer of the previous node, and the fake front box is a dummy node.