Intersection Point of Two Linked Lists in DSA Java - Deep Dive

Overview - Intersection Point of Two Linked Lists

What is it?

Given two singly linked lists that may share a common tail, find the node where they first merge. Both lists point to the same node object — not just the same value — so the intersection is a physical junction in memory where one reference sequence meets another. In Java, this means the same object reference, checkable with == not .equals().

Why it matters

This problem trains you to think about reference identity vs value equality, a distinction especially important in Java where == compares references and .equals() compares values. It also introduces two-pointer synchronization, a technique that reappears in cycle detection, palindrome checking, and sliding window problems.

Where it fits

You need to be comfortable with linked list traversal and Java object references before tackling this. After mastering this, you are ready for Floyd's cycle detection, merging sorted lists, and clone with random pointer problems.

Mental Model

Core Idea

If two runners start from different points but travel the same total distance by switching paths, they will meet exactly at the intersection.

Think of it like...

Imagine two hiking trails of different lengths that merge onto a single shared path. If hiker A walks trail A then trail B, and hiker B walks trail B then trail A, both cover the same total distance. They step onto the shared path at exactly the same moment.

List A:  1 → 3 → 5 ─┐
                       ├→ 8 → 10 → null
List B:  2 → 4 ─────┘

Pointer pA: 1→3→5→8→10→null → 2→4→[8] ✓
Pointer pB: 2→4→8→10→null → 1→3→5→[8] ✓
Both reach node 8 simultaneously.

Build-Up - 6 Steps

1

Foundation

Understanding the Problem — Reference Identity in Java

Concept: Intersection means the same object reference (==), not equal values (.equals()).

Two linked lists intersect when a node in list A IS the same object as a node in list B — same heap address. In Java, this is checked with pA == pB, not pA.val == pB.val. All nodes after the intersection are also shared. Two nodes with val=8 in different lists do NOT intersect unless they are the same Java object.

Result

You can distinguish a true intersection from coincidental equal values in Java.

Java's reference vs value equality distinction is the single most critical conceptual point here — == on objects checks identity, not equality.

2

Foundation

Brute Force — Check Every Pair

Concept: For each node in list A, scan all of list B for a matching reference.

Loop through every node in list A. For each node, loop through every node in list B. If nodeA == nodeB (same reference), return that node. Time O(m×n), space O(1). This confirms your understanding of reference equality before optimizing.

Result

Correct baseline solution but O(m×n) time is too slow.

Seeing brute force work via == confirms reference identity is the right check, building confidence for the optimized approach.

3

Intermediate

Length Difference Approach

🤔Before reading on: if list A has length 6 and list B has length 4, where should each pointer start so they reach the end at the same time? Commit to your answer.

Concept: Advance the pointer of the longer list by the length difference, then walk both in sync.

Compute lenA and lenB by traversing both lists. If lenA > lenB, advance pA by (lenA - lenB) steps. Now both pointers are equidistant from the end. Walk both one step at a time. The first node where pA == pB is the intersection. Time O(m+n), space O(1).

Result

Efficient O(m+n) solution after alignment.

Aligning tails by length removes the offset — once aligned, the first common reference must be the intersection.

4

Intermediate

Two-Pointer Path-Swap Technique

🤔Before reading on: if pA travels list A then list B, and pB travels list B then list A, do they cover the same total distance? Commit yes or no.

Concept: When a pointer reaches null, redirect it to the head of the other list.

Start pA at headA and pB at headB. Each step advance both. When pA reaches null, set pA = headB. When pB reaches null, set pB = headA. Continue until pA == pB. Both travel lenA + lenB total steps, arriving at the intersection simultaneously. If no intersection, both reach null together.

Result

Elegant O(m+n) time, O(1) space with no explicit length computation.

The path swap equalizes total travel: a + b == b + a. No length variables needed — the symmetry handles the offset automatically.

5

Advanced

Handling No Intersection

🤔Before reading on: what happens to pA and pB in the path-swap approach when the lists do not intersect? Commit to your answer.

Concept: Both pointers reach null at the same step when there is no intersection.

If no intersection exists, pA and pB both become null after traversing both lists. The loop condition pA != pB terminates because null == null is true in Java. Return null to indicate no intersection. No special case or counter needed.

Result

The same loop handles both intersecting and non-intersecting cases.

null == null evaluates to true in Java, so the no-intersection case terminates cleanly without any extra logic.

6

Expert

HashSet Approach — Space-Time Tradeoff

🤔Before reading on: can you store all nodes of list A in a HashSet and check list B against it? What is the space cost? Commit to your answer.

Concept: Store all node references from list A in a HashSet, then scan list B.

In Java: Set visited = new HashSet<>(). Traverse list A adding each node. Then traverse list B — the first node found in visited is the intersection. Time O(m+n), space O(m). Uses default reference-based hashCode/equals of objects, so no override needed. Simpler to implement but uses extra memory.

Result

Correct O(m+n) solution at O(m) space cost.

Java's default hashCode is identity-based for objects, so HashSet naturally stores references — no equals() override required.

Under the Hood

The two-pointer path-swap works because pA travels lenA + lenB steps and pB travels lenB + lenA steps. Both cover identical total distance. If an intersection exists at distance d from the end, both arrive at it after exactly lenA + lenB - d steps. The offset from different starting positions is cancelled by the path swap.

Why designed this way?

Linked lists lack random access so index-based alignment is impossible without traversal. The path-swap avoids explicit length computation by exploiting arithmetic symmetry: a + b == b + a. This is the same insight behind Floyd's cycle detection — two pointers with mathematically guaranteed meeting points replace brute comparison.

Step-by-step (A:1→3→5→8→10, B:2→4→8→10):

Step  pA         pB
  0    1          2
  1    3          4
  2    5          8
  3    8         10
  4   10        null→headA=1
  5  null→headB=2   1
  6    2          3
  7    4          5
  8   [8]        [8]  ← pA == pB (same reference)

Myth Busters - 4 Common Misconceptions

Quick: in Java, does pA.val == pB.val confirm intersection? Commit yes or no.

Common Belief: Two nodes intersect if pA.val == pB.val.

Reality: Intersection requires pA == pB (same object reference), not equal values. Different nodes can hold the same value without being the same object.

Why it matters: Using .val equality produces wrong answers on lists with duplicate values — a common Java mistake when confusing == semantics.

Quick: do the two pointers meet after exactly lenA steps? Commit yes or no.

Common Belief: The pointers meet after one of them finishes its own list.

Reality: They meet after each has traversed both lists combined — after lenA + lenB - intersectionDepth steps total.

Why it matters: Misunderstanding the meeting point leads to incorrect loop termination and off-by-one bugs in the implementation.

Quick: does the path-swap loop run forever when no intersection exists? Commit yes or no.

Common Belief: The algorithm loops infinitely when no intersection exists.

Reality: Both pointers become null simultaneously after traversing both lists, and null == null is true in Java, terminating the loop.

Why it matters: Adding a loop counter or break condition to handle this 'edge case' is unnecessary and can introduce bugs.

Quick: do you need to override hashCode() and equals() in ListNode to use HashSet? Commit yes or no.

Common Belief: Using ListNode in a Java HashSet requires overriding hashCode() and equals().

Reality: Java's default hashCode() and equals() use object identity, so HashSet correctly stores distinct node references without any override.

Why it matters: Overriding equals() to compare values would break the HashSet approach by merging nodes with equal values into one entry.

Expert Zone

1

The path-swap requires exactly one redirection per pointer — redirecting a second time breaks distance symmetry and causes an infinite loop or wrong answer.

2

If both lists have equal length, the pointers stay naturally synchronized from the start and the first common reference is found in the first pass without any redirect.

3

The problem assumes acyclic lists. If cycles exist, the null-redirect never triggers and the loop runs forever. Run cycle detection first if input validity is not guaranteed.

When NOT to use

If input lists may contain cycles, the path-swap breaks since pointers never reach null. Use HashSet or break cycles first. If code clarity matters more than memory in an interview setting, HashSet is simpler to explain and equally correct.

Production Patterns

Reference intersection detection appears in Java memory profiling tools (heap graph analysis), dependency injection frameworks (detecting shared bean references), and compiler design (CSE — common subexpression elimination). The two-pointer path-swap generalizes to any problem where two traversal sequences must be synchronized by their distance from a shared endpoint.

Connections

Floyd's Cycle Detection

Both use two-pointer synchronization with mathematically guaranteed meeting points rather than brute comparison.

Understanding intersection detection makes Floyd's algorithm intuitive — both exploit pointer arithmetic to force convergence.

Java Reference Equality (==)

The entire problem hinges on Java's == checking object identity, not .equals() checking value equality.

This problem is a practical drill on one of Java's most important and misunderstood distinctions — mastering it here prevents bugs across all reference-based data structures.

Clone Linked List with Random Pointer

Both require tracking node identity across two linked structures.

The identity-tracking mindset built here directly applies to cloning — you must map original nodes to clones by reference, not value.

Common Pitfalls

#1 Using .val == .val instead of == for intersection check.

Wrong approach:

while (pA != null && pB != null) {
if (pA.val == pB.val) // WRONG — value comparison
return pA;
pA = pA.next;
pB = pB.next;
}

Correct approach:

while (pA != pB) { // Correct — reference comparison
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;

Root cause:

Confusing value equality with reference equality — a fundamental Java pitfall when == on primitives (int) and == on objects mean different things.

#2 Redirecting after advancing past null, causing headB's first node to be skipped.

Wrong approach:

pA = pA.next;
if (pA == null) {
pA = headB;
pA = pA.next; // WRONG — skips headB
}

Correct approach:

pA = (pA == null) ? headB : pA.next;
// Redirect is part of the advance expression, not after it

Root cause:

Separating the null check from the advance causes the first node of the other list to be skipped, breaking distance symmetry by one step.

#3 Not guarding against null inputs.

Wrong approach:

ListNode pA = headA, pB = headB;
while (pA != pB) { // NullPointerException if headA or headB is null
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}

Correct approach:

if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;

Root cause:

Without null guards, passing an empty list causes the redirect to never fire and the loop to dereference null on the first iteration.

Key Takeaways

Intersection means the same Java object reference (==), not equal values (.equals()) — always use == on ListNode objects, never .val comparison.

The path-swap two-pointer technique equalizes total travel distance so both pointers arrive at the intersection simultaneously without computing list lengths.

In Java, null == null is true, so both pointers reaching null simultaneously terminates the loop cleanly when no intersection exists — no special case needed.

Java's default hashCode() uses object identity, making HashSet work correctly for the space-tradeoff approach without any override.

The path-swap generalizes: whenever two sequences must synchronize at a shared endpoint, equalize total distance by having each traverse both sequences.

Practice

1. What does the term intersection point of two linked lists mean?

easy

A. The node where both linked lists share the same reference (memory address).

B. The node where the values of both linked lists are equal.

C. The first node of the longer linked list.

D. The last node of the shorter linked list.

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (memory address) to the next node.

2. Step 2: Define intersection point

   The intersection point is where two linked lists share the exact same node reference, meaning they merge at that node.

3. Final Answer:

   The node where both linked lists share the same reference (memory address). -> Option A

4. Quick Check:

   Intersection means shared node reference [OK]

Hint: Intersection means same node object, not just same value [OK]

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is about list length
• Assuming intersection is always at the last node

2. Which of the following Java method signatures correctly represents a function to find the intersection point of two singly linked lists?

easy

A. public ListNode getIntersectionNode(int headA, int headB)

B. public void getIntersectionNode(ListNode headA, ListNode headB)

C. public int getIntersectionNode(ListNode headA, ListNode headB)

D. public ListNode getIntersectionNode(ListNode headA, ListNode headB)

Solution

1. Step 1: Understand method return type

   The method should return the intersecting node, so return type must be ListNode.

2. Step 2: Check parameter types

   Parameters must be the heads of the two linked lists, which are ListNode references.

3. Final Answer:

   public ListNode getIntersectionNode(ListNode headA, ListNode headB) -> Option D

4. Quick Check:

   Return node, input heads as ListNode [OK]

Hint: Return the intersecting node, input heads as ListNode [OK]

Common Mistakes:

• Using void return type instead of ListNode
• Using primitive types instead of ListNode
• Incorrect parameter types

3. Consider the following Java code snippet to find the intersection point of two linked lists:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}

If the two linked lists intersect at node with value 8, what will be the output when printing getIntersectionNode(headA, headB).val?

medium

A. 0

B. 8

C. null

D. Runtime error

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers traverse each list; when one reaches end, it switches to the other list's head. They meet at intersection.

2. Step 2: Identify intersection value

   Since lists intersect at node with value 8, pointers meet there and return that node.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Two-pointer meet at intersection node value 8 [OK]

Hint: Two pointers meet at intersection node value [OK]

Common Mistakes:

• Assuming output is null if lists differ in length
• Confusing node value with node reference
• Not understanding pointer switching logic

4. The following code attempts to find the intersection point of two linked lists but has a bug:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

What is the main problem with this code?

medium

A. It does not handle different list lengths, causing NullPointerException.

B. It uses incorrect comparison operator for nodes.

C. It returns the wrong node even if lists intersect.

D. It modifies the original lists, which is not allowed.

Solution

1. Step 1: Analyze pointer movement

   Both pointers move forward without switching lists, so if lengths differ, one pointer reaches null first.

2. Step 2: Identify error cause

   When one pointer is null and the other is not, accessing next causes NullPointerException.

3. Final Answer:

   It does not handle different list lengths, causing NullPointerException. -> Option A

4. Quick Check:

   Different lengths cause null access error [OK]

Hint: Handle different lengths by switching pointers [OK]

Common Mistakes:

• Ignoring list length difference
• Assuming nodes with same value are intersection
• Not checking for null before accessing next

5. You have two singly linked lists that intersect. List A has length 5, List B has length 7. Which approach correctly finds the intersection point in O(n) time without extra space?

hard

A. Use a hash set to store nodes of List A, then check nodes of List B.

B. Reverse both lists and compare nodes from the start.

C. Calculate lengths, advance longer list by difference, then move both pointers together.

D. Traverse both lists simultaneously without adjusting for length difference.

Solution

1. Step 1: Calculate lengths and difference

   Find lengths of both lists and compute difference (7 - 5 = 2).

2. Step 2: Advance longer list pointer

   Move pointer of longer list (List B) ahead by difference to align both pointers equally from intersection.

3. Step 3: Move both pointers together to find intersection

   Advance both pointers one step at a time until they meet at intersection node.

4. Final Answer:

   Calculate lengths, advance longer list by difference, then move both pointers together. -> Option C

5. Quick Check:

   Align pointers by length difference for O(n) solution [OK]

Hint: Advance longer list by length difference before simultaneous traversal [OK]

Common Mistakes:

• Using extra space like hash sets (not O(1) space)
• Reversing lists which is inefficient and modifies data
• Not adjusting for length difference causing wrong results