linked-list interview question

This was the question asked in intervie开发者_开发技巧w.Can anybody help me out it in implementing in java Given 2 linked lists(which need not have unique elements) find intersection point in the form of Y.(it can be anywhere--middle or tail)

If the length of the lists is O(N), this solution is O(N) with O(1) space.

FUNCTION length(LIST list) : INT
// returns number of nodes until the end of the list

FUNCTION skip(LIST list, INT k) : LIST
// return the sublist of list, skipping k nodes

FUNCTION intersection(LIST list1, list2) : LIST
// returns the sublist where the two lists intersects
  INT n1 = length(list1);
  INT n2 = length(list2);

  IF (n1 > n2) THEN
     list1 = skip(list1, n1-n2)
  ELSE
     list2 = skip(list2, n2-n1)

  WHILE (list1 != list2)
    list1 = skip(list1, 1)
    list2 = skip(list2, 1)

  RETURN list1

Essentially, traverse each lists to find how many nodes there are. Then, skip enough elements from the longer list so that now you have lists of the same length. Then, in-sync, move forward step-by-step until the two lists meet.

http://java.sun.com/docs/books/tutorial/collections/interfaces/set.html

I don't have a good example at the moment, but I believe he's referring to this:

"The intersection of two sets is the set containing only the elements common to both sets."

Where 'sets' can also be Lists, etc.

Java has built in methods for this.

Say you have a List list, you would do something like this:

list.removeAll(list2);

or

list.retainAll(list2);

retainAll will you give you the 'intersection', removeAll gives you the difference between the two lists.

According to @Lord Torgamus question, here is a suggested java algorithm.

Suppose you have two java Collection objects (and LinkedList, as an implementor of List, is also an implementor of Collection). To find their intersection, you only have to call Collection#retainAll method on the first object giving the second one as an argument.