c - Finding the intersecting node from two intersecting linked lists

Question

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list.

The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the list before they intersect are unknown and both list may have it different i.e. List1 may have n nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be

• m = n,
• m < n or
• m > n

One known or easy solution is to compare every node pointer in the first list with every other node pointer in the second list by which the matching node pointers will lead us to the intersecting node. But, the time complexity in this case will O(n²) which will be high.

What is the most efficient way of finding the intersecting node?

Answer 1

This takes O(M+N) time and O(1) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)

1. Traverse the two linked list to find M and N.
2. Get back to the heads, then traverse |M − N| nodes on the longer list.
3. Now walk in lock step and compare the nodes until you found the common ones.

---

Edit: See more here.