Interview Question for Software Development Engineer at Yahoo:

How do you find duplicate? Using bitmaps or hash right?

reversing a linked list is O(n) if you are allowed to keep a second linked list with the opposite data. Finding a duplicate node in a linked list can be done using a Hash, yes, or bitmaps (a little more work). But ideally, I think I would iterate the tree and store them into a heap of some sort and then pop the top of the heap and have the answer. This is O(n) to iterate and O(log n) to insert into the heap. If you were to use a Hash you would have to populate the hash, and then iterate over the hash to find the largest key->value pair (and iteration of a Hash is O(n)).

Thus,
Time to iterate linked list = T_LL = O(n)
Time to iterate hash = T_H = O(n)
Time to insert to heap = T_Heap = O(log n)
and Time to access root node (max occurrences in Heap) = T_H_Access = O(1)

Clearly T_LL + T_H > T_Heap + T_H_Access

I am sure more ways exist! This just illustrates the work for 2 ways.

ummm it's much simpler than that Mike.

Reverse the list:

public void reverse(final List<Node> list) {
    Node prev = null;
    Node next = list.head;
    Node n = list.head;
    while(next != null) {
        next = n.next;
        n.next = prev;
        prev = n;
        n = next;
    }
}

as you can see, you don't need a second list. this will run in O(n) time.

Also for finding the duplicate. Just use a hash map. on average you get O(1) for insertion into the map and you don't even need to go through the entire list as the question only asks to find "a" duplicate node. so something like this.

public Node findDuplicate(final List<Node> list) {
    final Map<Node, Node> map = new HashMap<Node, Node>();
    for(final Node n : list) {
        if(map.contains(n)) return n;
        else map.put(n, n);
    }
}

Worst case run the loop n times each contains check worst case O(n) but average should be O(1). So your best case runtime for the whole thing should be O(n), and worst case O(n^2).