Find Intersection of Two Linked Lists

leetcode.com

One of the most elegant Linked List problems asked in coding interviews is "Intersection of Two Linked Lists."

At first glance, it looks like a length-comparison problem. But the optimal solution uses a clever two-pointer technique that eliminates the need for length calculation entirely.

Let's break it down step by step.

---

Problem Statement

Given the heads of two singly linked lists, return the node at which the two lists intersect.

If the two linked lists have no intersection, return null.

Example

List A: 4 → 1 → 8 → 4 → 5
                ↑
List B: 5 → 6 → 1
                ↓
                8 → 4 → 5

Output

8

Because both lists merge at node 8.

---

Brute Force Approach

Interview Explanation

A straightforward approach is to compare every node of the first list with every node of the second list.

For each node in List A, traverse the entire List B and check whether both node references are the same.

This works because an intersection means both pointers point to the exact same node in memory, not just the same value.

Time Complexity

O(M × N)

Space Complexity

O(1)

Java Code

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    ListNode a = headA;

    while (a != null) {

        ListNode b = headB;

        while (b != null) {

            if (a == b) {
                return a;
            }

            b = b.next;
        }

        a = a.next;
    }

    return null;
}

---

Better Approach: HashSet

Interview Explanation

Store all nodes of the first linked list inside a HashSet.

Then traverse the second linked list. The first node already present in the HashSet is the intersection node.

Since HashSet provides O(1) lookup on average, this significantly improves the performance.

Time Complexity

O(M + N)

Space Complexity

O(M)

Java Code

import java.util.HashSet;

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    HashSet<ListNode> set = new HashSet<>();

    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }

    while (headB != null) {

        if (set.contains(headB)) {
            return headB;
        }

        headB = headB.next;
    }

    return null;
}

---

Optimal Approach: Two Pointer Technique

This is the solution most interviewers expect.

The beauty of this approach is:

• No HashSet
• No Length Calculation
• Constant Space
• Elegant Logic

---

Key Observation

Suppose:

Length of A = m
Length of B = n

Because lengths are different, two pointers starting from the heads may not reach the intersection at the same time.

So how do we remove this difference?

---

The Trick

Start two pointers:

p1 = headA
p2 = headB

Move both one step at a time.

Whenever a pointer reaches the end:

• p1 starts from headB
• p2 starts from headA

Eventually:

p1 travels = A + B
p2 travels = B + A

Both pointers travel exactly the same distance.

Therefore:

• If an intersection exists → they meet there.
• If no intersection exists → both become null together.

---

Why Does This Work?

Consider:

A: 1 → 2 → 3 → 8 → 9
B: 4 → 5 → 8 → 9

Initially, one pointer has a longer path before reaching the common portion.

After switching lists:

p1 covers remaining distance of B
p2 covers remaining distance of A

The difference in lengths automatically cancels out.

Both pointers eventually arrive at the same node.

---

Dry Run

Input

A: 4 → 1 → 8 → 4 → 5

B: 5 → 6 → 1 → 8 → 4 → 5

Initial State

p1 = 4
p2 = 5

Move both pointers.

When p1 reaches null

p1 = headB

When p2 reaches null

p2 = headA

Now both have traversed equal total distance.

Eventually:

p1 == p2 == node(8)

Return node 8.

---

Optimal Java Solution

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {

            p1 = (p1 == null) ? headB : p1.next;
            p2 = (p2 == null) ? headA : p2.next;
        }

        return p1;
    }
}

---

Complexity Analysis

Time Complexity

O(M + N)

Each pointer traverses at most both lists once.

Space Complexity

O(1)

No extra data structure is used.

---

Interview Follow-Up

Why do we compare p1 == p2 instead of p1.val == p2.val?

Because intersection means both pointers refer to the exact same node object in memory.

Different nodes can have identical values.

Example:

1 → 2 → 3

4 → 2 → 3

These lists are not intersecting even though values match.

---

Takeaway

Instead of calculating the length difference, make both pointers travel the same total distance (A + B). Once the distance becomes equal, they either meet at the intersection node or at null.

This is one of those interview solutions that feels like magic the first time you see it, but once understood, you'll never forget it.