Remove Dups.md

Provided code

Let's assume we're given the following Node class:

class Node { // public variables for simplicity
    Node next = null;
    int data = 0;
}

Solution

void removeDuplicates(Node head) {
    Set<Integer> set = new HashSet();
    set.add(head.data);
    Node n = head;
    while (n.next != null) {
        if (set.contains(n.next.data)) {
            n.next = n.next.next;
        } else {
            set.add(n.next.data);
            n = n.next;
        }
    }
    return;
}

Time/Space Complexity

• Time Complexity: O(n)
• Space Complexity O(n)

Alternate Solution

• Brute-force compare all pairs (Advantage is low space complexity). Use 1 pointer to walk list, and another pointer to check all remaining nodes each time.
• Time Complexity: O(n²)
• Space Complexity: O(1)