Intersection Point of Two Linked Lists in DSA C++ - 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 in memory — not just equal values — so intersection means the same pointer address. In C++, this is checked with pointer equality (pA == pB), which compares addresses, not dereferenced values (*pA == *pB).

Why it matters

This problem sharpens your understanding of raw pointer semantics in C++ — a critical skill for systems programming, embedded development, and memory management. The two-pointer path-swap technique also appears in cycle detection, string alignment, and sliding window problems.

Where it fits

You need comfort with C++ pointers, struct/class node definitions, and linked list traversal before tackling this. After mastering it, Floyd's cycle detection, merging sorted lists, and clone with random pointer follow naturally.

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

Two roads of different lengths merge onto one shared highway. Driver A takes road A then road B; driver B takes road B then road A. Both drive the same total distance and enter the shared highway at exactly the same moment.

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

pA: 1→3→5→8→10→nullptr → 2→4→[8] ✓
pB: 2→4→8→10→nullptr → 1→3→5→[8] ✓
Both reach node 8 (same address) simultaneously.

Build-Up - 6 Steps

1

Foundation

Pointer Identity in C++ — Address vs Value

Concept: Intersection means the same memory address (pA == pB), not equal node values (*pA == *pB or pA->val == pB->val).

In C++, pA == pB compares the addresses held by the two pointers. If both pointers hold the same address, they point to the same ListNode object. All nodes after the intersection are also shared because they are reached through the same pointer. Two nodes at different addresses with the same val do NOT intersect.

Result

You can reliably distinguish a true memory intersection from coincidental value equality.

C++ pointer equality is address comparison by default — no operator overloading needed. This makes intersection detection clean but requires discipline to not accidentally compare values instead.

2

Foundation

Brute Force — O(m×n) Address Comparison

Concept: For each node in list A, scan all of list B checking pointer equality.

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

Result

Correct baseline but prohibitively slow for large lists.

Seeing brute force work via pointer equality (not value comparison) locks in the correct mental model before optimization.

3

Intermediate

Length Difference Approach

🤔Before reading on: if list A has 6 nodes and list B has 4 nodes, how many steps should pA advance before you start walking both in sync? Commit to your answer.

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

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

Result

Efficient O(m+n) solution after tail alignment.

Once aligned at equal distance from the end, the first common address must be the intersection — no further tracking needed.

4

Intermediate

Two-Pointer Path-Swap Technique

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

Concept: When a pointer hits nullptr, redirect it to the head of the other list.

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

Result

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

lenA + lenB == lenB + lenA — the path swap exploits arithmetic symmetry to cancel the starting offset without any explicit measurement.

5

Advanced

No Intersection — nullptr == nullptr

🤔Before reading on: what do pA and pB both equal when there is no intersection and both have traversed both lists? Commit to your answer.

Concept: Both pointers become nullptr simultaneously when no intersection exists.

If no intersection exists, after each pointer traverses both lists, pA == nullptr and pB == nullptr at the same step. Since nullptr == nullptr is true in C++, the loop condition pA != pB evaluates to false and the loop exits cleanly. Return nullptr.

Result

The same loop handles both intersecting and non-intersecting cases — no special case needed.

nullptr == nullptr is guaranteed in C++ (all null pointers compare equal), so the termination condition works without any extra counter or flag.

6

Expert

Unordered_set Approach — Space Tradeoff

🤔Before reading on: can you store all node addresses from list A in an unordered_set and check list B against it? What is the space cost? Commit to your answer.

Concept: Store all raw pointers from list A in an unordered_set, then scan list B.

In C++: unordered_set visited. Traverse list A adding each pointer. Then traverse list B — the first pointer found in visited is the intersection. Time O(m+n), space O(m). unordered_set hashes by pointer address by default, so no custom hash needed for raw pointers.

Result

Correct O(m+n) solution at O(m) space — simpler to implement but uses extra memory.

C++ unordered_set uses std::hash which hashes pointer addresses — exactly what we need. No specialization required.

Under the Hood

The path-swap works because pA travels lenA + lenB steps and pB travels lenB + lenA steps — identical totals. If an intersection exists at distance d from the tail, both arrive at address of that node after lenA + lenB - d steps. The different starting offsets are exactly cancelled by the single redirect each pointer performs.

Why designed this way?

C++ linked lists lack random access, so index-based alignment requires traversal. The path-swap avoids explicit length computation by exploiting symmetry. This mirrors Floyd's cycle detection — two pointers with mathematically guaranteed convergence replace brute comparison. The approach also works in C because raw pointer equality is address comparison in both languages.

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

Step  pA           pB
  0    0x101(1)     0x201(2)
  1    0x102(3)     0x202(4)
  2    0x103(5)     0x301(8)
  3    0x301(8)     0x302(10)
  4    0x302(10)    nullptr→headA
  5    nullptr→headB  0x101(1)
  6    0x201(2)     0x102(3)
  7    0x202(4)     0x103(5)
  8    0x301(8) == 0x301(8)  ← pA == pB ✓

Myth Busters - 4 Common Misconceptions

Quick: does pA->val == pB->val confirm intersection in C++? Commit yes or no.

Common Belief: Two nodes intersect if their val fields are equal.

Reality: Intersection requires pA == pB (same address). Nodes at different addresses can have identical val fields without being the same object.

Why it matters: Comparing val instead of pointers produces wrong answers on any list with duplicate values — a subtle C++ bug that compiles without warning.

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

Common Belief: The algorithm loops infinitely when lists don't intersect because redirects keep happening.

Reality: After each pointer traverses both lists, both become nullptr simultaneously. nullptr == nullptr is true so pA != pB is false and the loop exits.

Why it matters: Adding a manual step counter or visited-flag guard is unnecessary and introduces complexity that can mask real bugs.

Quick: is *pA == *pB the correct intersection check? Commit yes or no.

Common Belief: Dereferencing and comparing (*pA == *pB) checks intersection.

Reality: This compares node contents (val, next), not addresses. Two distinct nodes with the same val and same next pointer would incorrectly appear to intersect.

Why it matters: Dereferencing adds UB risk if either pointer is nullptr, and the comparison logic is semantically wrong for intersection detection.

Quick: do you need a custom hash to use ListNode* in unordered_set? Commit yes or no.

Common Belief: Raw pointers need a custom hash specialization to work in unordered_set.

Reality: C++ provides std::hash for all pointer types by default, hashing the address. No specialization needed for raw pointer sets.

Why it matters: Writing a custom hash wastes time and risks errors — knowing the standard library handles raw pointers is a practical C++ skill.

Expert Zone

1

The path-swap requires exactly one redirect per pointer. If either pointer gets redirected twice the distance symmetry breaks and the loop either never terminates or returns the wrong node.

2

If both lists have equal length, the pointers stay naturally synchronized from step one and the first common address is found in the initial pass with no redirect.

3

The problem assumes acyclic lists. If either list has a cycle, pA or pB will never reach nullptr so the redirect never fires and the loop runs forever. Run cycle detection first if inputs are untrusted.

When NOT to use

If lists may contain cycles, use unordered_set or break cycles first. If RAII smart pointers (shared_ptr, unique_ptr) are used instead of raw pointers, equality semantics differ — shared_ptr == compares managed pointer addresses, which still works, but unique_ptr cannot be copied into a set without custom handling.

Production Patterns

Pointer intersection detection appears in C++ memory profilers (finding aliased allocations), compiler CSE passes (detecting shared subexpressions in ASTs), and custom allocator debugging. The path-swap principle generalizes to any two-sequence synchronization where a shared suffix must be located efficiently.

Connections

Floyd's Cycle Detection

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

Intersection detection and cycle detection share the same core insight: carefully chosen pointer movement rules force convergence without extra memory.

Raw Pointer Equality in C++

The entire problem hinges on C++ pointer == comparing addresses, not pointed-to values.

This problem is a practical drill on raw pointer semantics — the distinction between ptr == ptr (address) and *ptr == *ptr (value) is foundational for safe C++ code.

std::unordered_set with Pointer Keys

The hash set approach uses std::hash which hashes pointer addresses — the standard library's built-in support for raw pointer keys.

Knowing the standard library hashes raw pointers by address removes a common misconception and enables cleaner container usage in C++.

Common Pitfalls

#1 Comparing dereferenced values instead of pointer addresses.

Wrong approach:

while (pA && pB) {
if (pA->val == pB->val) // WRONG — value comparison
return pA;
pA = pA->next;
pB = pB->next;
}

Correct approach:

while (pA != pB) { // Correct — address comparison
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;

Root cause:

Confusing pointer equality (address) with value equality. In C++, pA == pB compares addresses; pA->val == pB->val compares data — they mean completely different things.

#2 Redirecting after advancing past nullptr, skipping headB's first node.

Wrong approach:

pA = pA->next;
if (!pA) {
pA = headB;
pA = pA->next; // WRONG — skips headB
}

Correct approach:

pA = pA ? pA->next : headB;
// Redirect is part of the ternary advance, not a separate post-step

Root cause:

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

#3 Not guarding against null input lists.

Wrong approach:

ListNode* pA = headA, *pB = headB;
while (pA != pB) {
pA = pA ? pA->next : headB; // UB if headA was nullptr and headB is too
pB = pB ? pB->next : headA;
}

Correct approach:

if (!headA || !headB) return nullptr;
ListNode* pA = headA, *pB = headB;
while (pA != pB) {
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;

Root cause:

If headA is nullptr, pA starts as nullptr and immediately redirects to headB on step one, which makes pA == headB while pB == headB only after full traversal — incorrect result.

Key Takeaways

Intersection means the same memory address (pA == pB in C++), not equal values — always compare pointers, never dereference for this check.

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

nullptr == nullptr is guaranteed in C++, so both pointers reaching nullptr simultaneously terminates the loop cleanly when no intersection exists.

unordered_set hashes by address by default in C++ — no custom hash needed for raw pointer sets.

The path-swap requires exactly one redirect per pointer — a second redirect breaks distance symmetry and causes incorrect results or infinite loops.

Practice

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

easy

A. The last node of each linked list.

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

C. The first node of the longer linked list.

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

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (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, not just the same value.

3. Final Answer:

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

4. Quick Check:

   Intersection means shared node reference = A [OK]

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

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is the last node always
• Assuming intersection means equal length lists

2. Which of the following C++ code snippets correctly declares a singly linked list node structure for intersection detection?

easy

A. struct Node { int data; Node* next; };

B. struct Node { int data; Node next; };

C. struct Node { int data; Node* next(){}; };

D. struct Node { int data; Node next(); };

Solution

1. Step 1: Understand pointer usage in C++ structs

   A linked list node must have a pointer to the next node, so Node* next; is correct.

2. Step 2: Analyze options

   struct Node { int data; Node* next; }; uses Node* next; which is correct. Options A, B, and D misuse pointer or function syntax.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option A

4. Quick Check:

   Pointer to next node = C [OK]

Hint: Use pointer (*) for next node in struct [OK]

Common Mistakes:

• Forgetting the * pointer for next node
• Using function syntax instead of pointer
• Declaring next as object instead of pointer

3. Given two linked lists intersecting at node with value 7, what will the following code print?

Node* getIntersectionNode(Node* headA, Node* headB) {
    Node* a = headA;
    Node* b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}

// Lists:
// A: 3 -> 6 -> 9 -> 7 -> 10
// B: 1 -> 7 -> 10

Node* intersection = getIntersectionNode(headA, headB);
if (intersection) std::cout << intersection->data << std::endl;
else std::cout << -1 << std::endl;

medium

A. -1

B. 10

C. 7

D. 3

Solution

1. Step 1: Understand the algorithm

   This code uses two pointers traversing both lists; when one reaches end, it switches to the other list's head. They meet at intersection.

2. Step 2: Trace the pointers

   Both pointers meet at node with value 7, which is the intersection point.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Intersection node data = 7 [OK]

Hint: Two-pointer switch method finds intersection node [OK]

Common Mistakes:

• Assuming intersection is node with value 10
• Printing -1 when intersection exists
• Confusing node value with node reference

4. Identify the bug in this code snippet that tries to find the intersection point of two linked lists:

Node* getIntersection(Node* headA, Node* headB) {
    while (headA != headB) {
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}

medium

A. It does not handle different list lengths, causing null pointer errors.

B. It uses incorrect comparison operator for nodes.

C. It returns the wrong node after loop ends.

D. It should use recursion instead of iteration.

Solution

1. Step 1: Analyze pointer movement

   The code moves both pointers forward simultaneously without adjusting for different list lengths.

2. Step 2: Identify consequence

   If lists differ in length, one pointer may reach null before the other, causing a null pointer dereference or infinite loop.

3. Final Answer:

   It does not handle different list lengths, causing null pointer errors. -> Option A

4. Quick Check:

   Unequal lengths cause errors = D [OK]

Hint: Adjust pointers for length difference before comparing [OK]

Common Mistakes:

• Ignoring list length difference
• Dereferencing null pointers
• Assuming simultaneous traversal always works

5. You have two singly linked lists that intersect. List A has length 8, List B has length 5. Which approach correctly finds the intersection point efficiently?

hard

A. Traverse both lists fully and store nodes in hash sets, then find first common node.

B. Calculate length difference, advance longer list by difference, then move both pointers together.

C. Reverse both lists and compare nodes from start until they differ.

D. Compare node values one by one from heads until a matching value is found.

Solution

1. Step 1: Understand length difference method

   Calculate difference (8 - 5 = 3), advance longer list by 3 nodes to align both lists.

2. Step 2: Traverse both lists together

   Move both pointers one step at a time; the first node where they match is the intersection.

3. Final Answer:

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

4. Quick Check:

   Align by length difference then traverse = B [OK]

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

Common Mistakes:

• Comparing node values instead of references
• Reversing lists unnecessarily
• Using extra space when not needed