## Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

- First find where the loop begins using 2x fast and normal pointers.
- Than find the length of each linked list considering the fact that the list ends when you encounter the loop point 2nd time it is the end.
- Than adjust the length of the long linked list so that it is the same length with the short one.
- Now start traversing both and see where they intersect.

Comment hidden because of low score. Click to expand.
0

A little improvement in step 2

-Once we find the starting of the loop, we can just measure the length of the 2 lists till we encounter that specific node (the starting node, we don't need to enter the loop).
-Calculate diff = length1 - length2
-Move (diff) no. of nodes forward in the longer list.
-Start moving in both the lists, once they point to the same node, we have reached the merging node.

Please correct me if am wrong.

Comment hidden because of low score. Click to expand.
0

You (me as well) have assumed that lists merge before the cycle node. They could be merging after the cycle node.

Comment hidden because of low score. Click to expand.
0

Find the loop node, make it as the point of reference for the linked list length calculation, it would need 3 iterations totally, one to find if there's a loop in the list, 2nd to find the looping node, 3rd to find the intersection point

Comment hidden because of low score. Click to expand.
0

There can be 2 loop nodes.

Comment hidden because of low score. Click to expand.
0

thanks for test case, i missed it, in such case there should be a check if the loop nodes of both the linked lists are same, else the nodes don't intersect.

Comment hidden because of low score. Click to expand.
0

Sun only thing you need to do if the loop nodes are the same. If they are different than you have to calculate lengths seperately than apply the algorithm thats all. They can intersect still if the loop nodes are different.

Comment hidden because of low score. Click to expand.
-1
of 5 vote

The loop must be present at or after the merge point . As if not , the list end will have to point to two different nodes which isnt possible .

Comment hidden because of low score. Click to expand.
0

It isn't possible? May be a drawing will make it clear. ww w.flashpaint.com/sketchit.php?id=14261

Comment hidden because of low score. Click to expand.
0

@ Rayden
The lists have to have a common tail. So, I agree with Ankur.

Comment hidden because of low score. Click to expand.
0

I did NOT say the loop nodes can be different. I simply stated that their loop "entry" nodes can be different.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1) Remove the loop if any .
2) Find the merged point .
3) Again form the loop .

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.