Prepare for interviews along with me. Find if two linked lists are merging.

I will be posting some interesting interview questions I was asked. Hopefully it may be of some help to you all.

1) Find if the two linked lists merge at any point? Find the node where they are intersecting?
Ans) There are many ways to do this problem. GeeksforGeeks.com has listed few solutions. I am giving the most efficient and easiest way here. For other kind of solutions you can do google search.

First we can check if two linked lists merge by checking if the last node of both the linked lists is same.

Second to find the node where they are merging, find the lengths of both linked lists. let it be L1 and L2.
The difference will be L1-L2 (assuming L1>L2. can take absolute value as well).
The node where they are merging is the (L1-L2)th node on smaller linked list.

You need to advance the pointer on longer linked list by (L1-L2) number of nodes. Then traverse on both the linked lists simultaneously. The place where the pointers meet is the merge point.
Time complexity O(m+n) where m and n is the length of two linked lists.

Few sources for code: http://geeksforgeeks.org/?p=2405
http://blogs.msdn.com/b/abhinaba/archive/2007/08/16/interesting-linked-list-problem.aspx
http://stackoverflow.com/questions/1826501/best-possible-algorithm-to-check-if-two-linked-lists-are-merging-at-any-point-if
http://stackoverflow.com/questions/1594061/linked-list-interview-question