Finding the intersection node of two singly linked lists

Problem

We are given a two singly linked lists and we need to find the node at which the lists intersect and become a single list. See the image below, we need to find the node marked with question mark.

Number of nodes in the given singly linked lists are unknown.

 

Solution

Step 1: Find the lengths of the two linked lists.

 

Step 2: Find the difference diff of the lengths.

 

Step 3: Take diff steps in the longer list.


Step 4: Step forward both the lists  in parallel until the links to next node match.


Step 5: If match found, return that matching node else return null.

Source Code