Intersection of Two Linked Lists (LC 160)

Pattern: Two Pointers / Length Equalization
Difficulty: Easy
Key Concept: Two walkers swap lists at the end so both travel the same total length and meet at the shared suffix (or both hit null).

Problem Statement

You are given the heads of two singly linked lists headA and headB. The lists may intersect at a node such that all nodes from that node to the end are shared (same object references, not merely equal values). Return the intersecting node, or null if they do not intersect.

Input: headA, headB (either may be null).

Output: The first shared ListNode, or null.

Notes: Intersection is defined by reference equality—the lists merge into one tail. There are no cycles.

---

1. Algorithm & Pseudocode

Brute force (HashSet of A’s nodes)

seen = empty set of ListNode
for p = headA; p != null; p = p.next:
    add p to seen
for p = headB; p != null; p = p.next:
    if seen contains p: return p
return null

Optimal (two pointers, switch lists at end)

pa = headA, pb = headB
while pa != pb:
    pa = (pa == null) ? headB : pa.next
    pb = (pb == null) ? headA : pb.next
return pa   // intersection node or both null

Why it works (length math)
Let unique part of A have length a, unique part of B have length b, common tail length c.
Pointer on A walks a + c, then b after switch → a + c + b.
Pointer on B walks b + c, then a after switch → b + c + a.
Both totals equal a + b + c, so they align at the start of the common tail (or both null if no intersection and no shared tail).

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Reference vs value
   The answer must be the same node object in both lists. In Java, use == between references, not equals() (unless equals is overridden to mean reference equality—which Object does by default, but == is clearer for “same node”).

2. Why HashSet works
   Store every address from list A, then walk B; the first node seen in the set is the merge point. Simple but O(n) memory.

3. Why two pointers work
   Without counting lengths explicitly, switching heads when a pointer hits null pads the shorter list with the longer list’s prefix, equalizing total steps—a compact mathematical trick.

4. No intersection
   Both traverse A then B (or B then A) and eventually both become null at the same time, so pa == pb with value null.

5. Beauty
   Same idea works in C++/Python: pointer/reference traversal with swap. The insight is algebraic, not language-specific.

---

3. The Dry Run

Structure (shared suffix starts at node n8 with value 8):

• List A: n4a → n1a → n8 → n4s → n5s
• List B: n5b → n6 → n1b → n8 → n4s → n5s

(n8, n4s, n5s are the same objects in both lists.)

Step	pa	pb	Notes
0	n4a	n5b
1	n1a	n6
2	n8	n1b
3	n4s	n8	different nodes
4	n5s	n4s
5	n5b	n5s	pa reached end of A → pa = headB; pb advanced to tail n5s
6	n6	n4a	pa from n5b; pb reached end of B → pb = headA
7	n1b	n1a
8	n8	n8	same reference — intersection

Return n8 (value 8). This matches lists A = [4,1,8,4,5] and B = [5,6,1,8,4,5] merging at the first 8.

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode p = headA; p != null; p = p.next) {
            seen.add(p);
        }
        for (ListNode p = headB; p != null; p = p.next) {
            if (seen.contains(p)) {
                return p;
            }
        }
        return null;
    }
}

Time: O(m + n). Space: O(m) for storing nodes of A (or O(max(m,n)) if you store the other list).

Optimal

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb) {
            pa = (pa == null) ? headB : pa.next;
            pb = (pb == null) ? headA : pb.next;
        }
        return pa;
    }
}

Time: O(m + n). Space: O(1).

---

5. The “Java vs. Others” Edge

• Use == for nodes: You want reference identity—pa != pb and pa == null are reference checks. This matches C pointer comparison for list nodes.
• No special pointer syntax: Java references behave like tracked pointers; there is no */&, which can make the algorithm easier to read for beginners.
• Math insight: Each pointer walks a + b + c steps before meeting at the merge (or both walk off the end). Same formula whether implemented in Java, C++, or Python.
• HashSet<ListNode>: Uses reference identity for hashCode/equals by default for object identity in the set (actually hashCode is identity-based unless overridden—LeetCode ListNode is typical). For clarity, seen.contains(p) still means “this exact node reference.”

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(m + n)	O(m)	HashSet of one list’s nodes; very straightforward.
Optimal	O(m + n)	O(1)	Two pointers; switch to other head at end of path.