## Problem

Contents

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int longLen = 0; int shortLen = 0; // Lets assume that the first list is longer than the second. Node longer = first (Head of the first list); Node shorter = second (Head of the second list); while(longer != null) { longLen++; longer = longer.getNext(); } while(shorter != null) { shortLen++; shorter = shorter.getNext(); } |

**Step 2:** Find the difference *diff* of the lengths.

1 |
int diffInLength = Math.abs(longLen - shortLen); |

**Step 3:** Take *diff *steps in the longer list.

1 2 3 4 |
for(int i = 0; i < diffInLength; i++) { // Skip the nodes in longer list till the length of two lists become equal. longer = longer.getNext(); } |

**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**.

1 2 3 4 5 6 7 |
while(longer != null && shorter != null) { if(longer == shorter) { return longer; } . . . |

## Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public Node findIntersection(Node first, Node second) { int longLen = 0; int shortLen = 0; // Lets assume that the first list is longer than the second. Node longer = first; Node shorter = second; while(longer != null) { longLen++; longer = longer.getNext(); } while(shorter != null) { shortLen++; shorter = shorter.getNext(); } if(longLen < shortLen) { // If our assumption is wrong, we update the pointers. longer = second; shorter = first; } else { // We initialize them back to the heads of their respective lists longer = first; shorter = second; } int diffInLength = Math.abs(longLen - shortLen); for(int i = 0; i < diffInLength; i++) { // Skip the nodes in longer list till the length of two lists become equal. longer = longer.getNext(); } while(longer != null && shorter != null) { if(longer == shorter) { return longer; } longer = longer.getNext(); shorter = shorter.getNext(); } return null; } |