Remove Duplicates in a sorted Linked List

The problem, simply

You get a linked list whose numbers are already sorted from small to big, like 1 -> 1 -> 2 -> 3 -> 3. Some numbers appear more than once.

Remove the extra copies so every number appears only once, and keep the order. Give back the head. Change the arrows; do not build a new chain.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a bag of numbers you have already seen, a set. Walk the chain. If the box's number is in the bag, unhook the box. If not, put the number in the bag and move on.

1. prev is the last box you kept. curr is the box you are checking.
2. If curr.val is in the bag, make prev.next skip over curr.
3. Otherwise add it to the bag and move prev to curr.

This works even when the chain is not sorted, which is exactly why it wastes the hint. It needs a bag as big as the chain.

import java.util.*;

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Set<Integer> seen = new HashSet<>();
        ListNode prev = null;
        for (ListNode curr = head; curr != null; curr = curr.next) {
            if (seen.contains(curr.val)) {
                prev.next = curr.next;   // unhook the copy, prev stays
            } else {
                seen.add(curr.val);      // first time we see this number
                prev = curr;
            }
        }
        return head;
    }
}

How long it takes: one walk, and each bag check is about one step, so O(n). Extra room: the bag can hold every number, O(n).

Way 2: the clever way

Because the chain is sorted, a copy is always the very next box. So you only compare each box with its neighbor.

1. Put curr on the head.
2. While curr and its next box exist: if they hold the same number, set curr.next = curr.next.next to skip the copy, and stay put. Otherwise move curr forward.
3. Give back the head.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                curr.next = curr.next.next;   // skip the copy, stay here
            } else {
                curr = curr.next;             // different, move on
            }
        }
        return head;
    }
}

How long it takes: every box is looked at once, either kept or skipped, O(n). Extra room: one finger, O(1).

Watch out for

• Check curr != null before curr.next, so the empty chain is safe.
• The head never changes in this problem, because the first box is always kept.
• In C or C++ you must free the skipped box. In Java the garbage collector cleans it up.

What interviewers ask next

• Remove every number that has copies, keeping only numbers that appear once (LeetCode 82). Now the head can disappear, so start with a dummy box before the head. For each run of equal numbers, if the run is longer than one, make the box before the run point past the whole run.
• What if the chain is not sorted? Copies are no longer neighbors. Use the bag of seen numbers (Way 1), or sort the chain first with merge sort.
• Can you do it with recursion? Clean the rest of the chain first, then if the head equals its new neighbor, return the neighbor. It uses O(n) stack room.
• Same idea on a sorted array (LeetCode 26)? Yes. A write finger and a read finger; write only when the number differs from the last written one.

Remember this

Grown-up words: the boxes are nodes, the bag of seen numbers is a hash set, skipping a box is changing its next pointer, and the fake front box is a dummy node.