Hi This was the question asked in interview.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)
+1
A:
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.
Riduidel
2010-05-05 15:07:29
+2
A:
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.
Freddy
2010-05-05 15:10:26
But then, what's the point part? I think he's underspecified the problem.
Joel
2010-05-05 15:13:15
I may have over-simplified his question in an effort to clarify. Perhaps it's a bit more complex given the 'point' part.
Freddy
2010-05-05 15:23:59
+5
A:
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.
polygenelubricants
2010-05-05 16:27:33
@polygenelubricants, how is this O(n) ? List comparison would be O(n) and you are doing this up to n times. For example run the above code with the lists {1,2,3,4} and {1,2,3,5}
Jasmeet
2010-05-06 05:24:50
Smart. @Jasmeet, `list1 != list2` is just doing an O(1) comparison of the addresses of these two list nodes, not performing an element-by-element comparison, so overall it is O(n). The key insight is that the intersection point must be the same distance from the end in both lists, so comparing corresponding elements is enough to find it.
j_random_hacker
2010-07-11 13:57:01