Interview Question

Financial Software Developer Interview

Given heads of two linked lists. Find if the two linked

  lists intersect. Solution should not use extra memory.
Answer

Interview Answer

7 Answers

0

Traverse through the linked lists to find their lengths 'm' and 'n'.
Skip |m-n| nodes from the larger list.
Now traverse through the two linked lists and it the addresses of two nodes are the same. This is the intersection point.

Time : O(n)
Space : O(1)

Interview Candidate on Mar 11, 2014
0

Why would you skip [m-n] nodes from the larger list, couldn't the address in memory of one of these nodes still intersect with a node in the shorter list?

Mike on Mar 13, 2014
0

The interviewer wanted a solution which used O(1) space.
If two lists intersect, they will have atleast one node in common.
Lets assume both lists are of the same size. If they intersect at node 3,
you can compare address[node 1 in list 1] and address of[node 1 in list 2].
This condition will be true at node 3.

However you cannot do this if both lists are of different sizes.
You will have to skip |m-n| nodes from larger list so that you reach a point where both lists are of equal sizes. Now you can compute as above.

Anonymous on Mar 13, 2014
0

Traverse to the end of both linked lists. If they are the same node, then some node on the list intersects. The reason for this is that if a single node anywhere intersects, all nodes beyond that must by definition be the same. This solution won't tell you where the two nodes intersect, just that they do or do not. O(N) run time, no extra space used.

The above solution is more complex but will tell you which node the intersection occurs in

Anonymous on Mar 14, 2014
0

Your solution is correct if we assume after the intersection point, all the nodes are common to both lists.

However, if there is a case where the lists intersect at one particular node and after that point they do not have any other node in common, we wont be able to detect the intersection point.

Anonymous on Mar 14, 2014
1

If 2 linked lists point to the same node, then by definition, all subsequent nodes MUST be the same. A linked list only has a single 'next' node, and that doesn't change depending on the previous node.

for example:
A) 1->2->3->4->5
B) 6->7->4->8

The above example is what you're talking about. And it can't exist. Node 4 cannot simultaneously point to both 5 and 8, it MUST point to a single next node (or even if it points to multiple next nodes, they must be the same for every linked list that contains 4)

Anonymous on Mar 15, 2014
0

There is no restriction on destroying the list so I would
1. Find the length of first list.
2. Destroy/break the links of the second list
3. Check the size of the first list.
4. If size if still the same then lists don't intersect otherwise they do. Edge case is that the lists intersect in the last element, so additional check is needed for that

Anonymous on May 20, 2014

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up