CODEWITHSUNDEEP
javalinked-list
Jesus
Jesus

Reputation: 31

Remove duplicates in list from Cracking the Coding Interview

From Cracking the Coding Interview. Problem 2.1: Write code to remove duplicates from an unsorted linked list. This is the solution that they provide:

public static void removeDuplicates(Node n) {
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    Node previous = n;
    while (n != null) {
    if (table.containsKey(n.data)) {
        previous.next = n.next;
    } else {
        table.put(n.data, true);
        previous = n;
    }
    n = n.next;
    }
}

My question is: When you do n=n.next, wouldn’t you lose the head of the list (first node)? How would you access to this list again with the duplicates removed if you don’t have access to the head?

And also isn’t it better to use a Set instead of a Table? I don’t think you need Key and Value. I think you only need the Key, right?

Thank you

Upvotes: 2

Views: 1334

Answers (2)

iwita
iwita

Reputation: 91

There is no return statement in the function, as it is set as void. However, if the head of the list is kept outside of the function in some variable, it is enough to return the correct result. That's because the first node is not going to be removed, as there will not be any duplicate at this time. After all, you don't have any problem with changing the n value.

Upvotes: 0

Gren
Gren

Reputation: 1854

First, as already mentioned in a comment, the change of the local parameter has no effects to the callers input-variable.
Second, you are right, using a Set would be better, but only because the code is better to read. The code is syntactically correct, internally a Set is nothing else than a Map with the same dummyobject as value for every key.

Upvotes: 1

Related Questions