3- How to detect if two singly linked lists have joined each other at some node ?

3-Ans- If the two singly Linked List join each other at some node, then they would have their last parts common and, obviously a common last node [node: 5 in the image below], i.e. they would look like the figure below:

Here are the steps to efficiently find out if really they have joined each other somewhere:

[The only inputs we have are the two pointers to the starting nodes: S1 and S2]

--a) First, find out the length of the first Linked List, let it be L1. Also keep track of the last node.

--b) Then, find out the length of the second list, let it be L2. Also compare the last node of this

list with the last node of the first list got in the previous step.

--c) If the two last nodes are not the same then we can safely say the two lists have NOT JOINED, hence return.

(Though in our image we see the last nodes are same, i.e. the node: 5)

--d) Otherwise select the longer length (L2 in this case) and calculate the value (L2 - L1).

--e) Advance the head node pointer of the longer list (S1 ) by (L2 - L1) steps.

(Note: if both lists are of same length, then (L2 - L1) will be zero.)

--f) Now, run a loop and for each iteration advance both the pointers (S1 and S2 ) by

one step each and compare them. Because, lists HAVE JOINED each other at some node,

at some point of time the pointers will definitely refer to the same location. As soon as they

refer to the same node, break out from the loop and return.