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?

8 Answers

▲

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?

▲

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.

▲

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

▲

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.

▲

2

▼

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)

▲

1

▼

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

▲

0

▼

use LinkedHashMap to find out first distinct element

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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)