Given heads of two linked lists. Find if the two linked lists intersect.
Solution should not use extra memory.

Question

Given heads of two linked lists. Find if the two linked lists intersect.
Solution should not use extra memory.

Sigiloso · Accepted Answer

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)

Sigiloso · Answer

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

Sigiloso · Answer

use LinkedHashMap to find out first distinct element

Sigiloso · Answer

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)

Mike · Answer

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?

Sigiloso · Answer

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.

Sigiloso · Answer

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

Sigiloso · Answer

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.

Bloomberg

Pergunta de entrevista da empresa Bloomberg

Respostas da entrevista

Empresas seguidas

Buscas de vagas