CareerCup

Well, there are several approaches to solve this problem.

Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list

Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.

while(head1)
{
cur2=head2;
while(cur2)
{
    if(cur2==head1)
        return cur2;
    cur2=cur2->next;
}
head1=head1->next;
}

Time Complexity: O(N*M)
Space Complexity: O(1)

Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].

Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.

Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 6: [A better approach]
1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)

Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)

1.) travel both the link lists and find out their length... (since after they merge the length would be same from point of merging ....)

so if both the lengths are same then traverse through both the lists one node at a time and go on comparing them....
if lengths are different then calculate the difference abs(length of A - length of B)

--- suppose the difference in length is X...

then travel X nodes in the longer linked list first....

and now travel 1 node at a time from both the list .... for shorter list from the starting and for longer list from the point after X nodes...

if the list is merging then you would get the point of merge

Time complexity O(n)

Here is the simple way of doing this
1. Find out lengths of both lists(Say List A and List B). This can be done in O(n)
2. Say lengths are a and b where a>b Now for for the bigger list traverse the node to next for (a-b). That if a is 10 and b is 8, Go to next node for List A twice,
3. Now start comparing the nodes one by one, when they are equal it is the merge point

So overall complexity is O(n)

Solution on Stackoverflow : stackoverflow.com/questions/1826501/best-possible-algorithm-to-check-if-two-linked-lists-are-merging-at-any-point-i

1. If list merge then last node of both list will be same
2. Now from last node, traverse both list in reverse and get the merge point

Keep moving both the pointers to next and check if they point to same address, if so then we get the merge point, if either of the pointers become null then we do not have any merge point between the two linked lists.

p1=head1;
p2=head2;
while(1)
{
if(p1 == null || p2 null) return null;
if(p1 == p2) return p1;
p1=p1->next;
p2=p2->next;

}

If I could tick the nodes like IsVisited=true, tick node and when either listA or listB found the ticked node, that could be the goal

public Node GetMergedPoint(Node rootA, Node rootB)
{
 while (rootA.Next != null && rootB.Next != null)
 {
  if (rootA.IsVisited) return rootA;;
  if (rootB.IsVisited) return rootB;

  rootA.IsVisited = true;
  rootA = rootA.Next;

  rootB.IsVisited = true;
  rootB = rootB.Next;
 }
 
 return null;
}