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. Intersection means the same memory address — both pointers hold the same struct Node* value. In C, pointer equality (pA == pB) directly compares addresses stored in the pointers, making this both efficient and explicit.

Why it matters

C has no automatic memory management, so understanding pointer identity vs value equality is foundational. This problem reinforces that two pointers can hold different addresses to structs with identical field values — they are not the same node. The two-pointer path-swap technique also appears in cycle detection, string processing, and buffer alignment problems in C.

Where it fits

You need comfort with C pointers, struct definitions, and manual linked list traversal before tackling this. After mastering it, Floyd's cycle detection, list reversal, and memory pool management follow naturally.

Mental Model

Core Idea

If two walkers start from different points but each walks both paths in sequence, they cover the same total distance and arrive at the shared section simultaneously.

Think of it like...

Two river tributaries of different lengths merge into one river. A boat starting on tributary A then tributary B, and another starting on B then A, both travel the same total distance and enter the merged river at exactly the same moment.

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

pA: 1→3→5→8→10→NULL → 2→4→[8] ✓
pB: 2→4→8→10→NULL → 1→3→5→[8] ✓
Both reach address of node 8 simultaneously.

Build-Up - 6 Steps

1

Foundation

Pointer Identity in C — Address Comparison

Concept: pA == pB compares the addresses stored in the two pointers, not the data at those addresses.

In C, a pointer variable holds a memory address. pA == pB is true only when both hold the exact same address — they point to the same struct Node in memory. To compare node data you would write pA->val == pB->val, which is a completely different check. Intersection requires address equality, not data equality.

Result

You can reliably detect a true memory intersection using simple pointer equality.

C makes this explicit — there is no implicit operator overloading. pA == pB is always address comparison, which is exactly what intersection detection needs.

2

Foundation

Brute Force — O(m×n) Nested Loop

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

Outer loop traverses list A node by node. Inner loop traverses list B. If pA == pB (same address), return that pointer. Time O(m×n), space O(1). This is correct but slow — useful only to confirm the pointer equality concept before optimizing.

Result

Correct baseline establishing that address comparison is the right check.

Verifying brute force locks in the concept: identical addresses = intersection. No further confirmation needed before applying the optimized technique.

3

Intermediate

Length Difference Approach

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

Concept: Advance the longer list's pointer by the length difference, then walk both one step at a time.

Count lenA and lenB with two traversals. If lenA > lenB, advance pA by (lenA - lenB). Both pointers are now equidistant from the tail. Walk pA and pB one step each iteration. 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 NULL, the first common address must be the intersection — the alignment eliminates the offset problem.

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 number of nodes? Commit yes or no.

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

Initialize pA = headA, pB = headB. Each step advance both. When pA == NULL, set pA = headB. When pB == NULL, set pB = headA. Continue until pA == pB. Both traverse lenA + lenB nodes total. They arrive at the intersection address at the same step. If no intersection, both reach NULL together.

Result

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

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

5

Advanced

No Intersection — NULL == NULL in C

🤔Before reading on: in C, is NULL == NULL guaranteed to be true? Commit yes or no.

Concept: Both pointers become NULL simultaneously when no intersection exists, terminating the loop.

If no intersection exists, after each pointer traverses both lists, pA == NULL and pB == NULL at the same step. In C, NULL is defined as (void*)0 or 0, and NULL == NULL is always true. So pA != pB evaluates to false and the while loop exits cleanly. Return NULL.

Result

No special case or counter needed — the same loop handles both cases.

C's NULL is a well-defined value (zero or null pointer constant). Two null pointers always compare equal, making the termination condition work universally.

6

Expert

Hash Table Approach — Space Tradeoff in C

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

Concept: Store all node pointers from list A in a hash table keyed by address, then scan list B.

In C, implement a simple hash table mapping (uintptr_t)node_ptr to 1. Traverse list A inserting each address. Traverse list B — the first address found in the table is the intersection. Time O(m+n), space O(m). Casting to uintptr_t makes pointer arithmetic well-defined for hashing. Simpler to reason about but requires dynamic allocation.

Result

Correct O(m+n) solution trading O(m) memory for simpler implementation.

Casting struct Node* to uintptr_t for hashing is the standard C idiom for pointer-keyed hash tables — it avoids undefined behavior from direct pointer arithmetic.

Under the Hood

The path-swap works because pA travels lenA + lenB nodes and pB travels lenB + lenA nodes — identical totals. If intersection exists at distance d from NULL, both arrive at that address after lenA + lenB - d steps. The different starting positions contribute lenA and lenB respectively to each pointer's first leg, and lenB and lenA to the second leg — the offset is exactly cancelled.

Why designed this way?

C linked lists are raw pointer chains with no built-in length. Computing lengths requires O(n) traversal, which the path-swap avoids entirely through symmetry. The technique also maps directly to assembly-level pointer manipulation, making it efficient on any architecture without overhead from library abstractions.

Step trace (A: 1→3→5→8→10, B: 2→4→8→10, addresses simplified):

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 ✓

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). pA->val == pB->val only compares data — two distinct nodes at different addresses can have identical values.

Why it matters: Comparing field values instead of addresses causes false positives on any list with duplicate values, producing wrong intersection nodes.

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

Common Belief: The loop runs infinitely because both pointers keep redirecting between the two lists.

Reality: Both pointers become NULL at the same step after traversing both lists. NULL == NULL is true in C so pA != pB is false and the loop exits.

Why it matters: Adding a manual step counter to prevent infinite loops is unnecessary and can incorrectly terminate the loop before finding the intersection.

Quick: is it safe to dereference pA inside the loop condition? Commit yes or no.

Common Belief: The loop condition can safely check *pA == *pB instead of pA == pB.

Reality: Dereferencing a NULL pointer is undefined behavior in C. When pA or pB reaches NULL at the end of a list, any dereference causes a crash or silent memory corruption.

Why it matters: Never dereference in a loop condition without a NULL guard. Always compare the pointers themselves (pA == pB) to avoid UB.

Quick: is casting a pointer to uintptr_t for hashing undefined behavior in C? Commit yes or no.

Common Belief: Converting a pointer to an integer for hashing is undefined behavior in C.

Reality: Casting to uintptr_t (defined in ) is explicitly safe in C — it is an unsigned integer type guaranteed to hold any pointer value without loss.

Why it matters: Using int or long for pointer-to-integer casts can truncate on 64-bit platforms. uintptr_t is the correct, portable type for pointer hashing in C.

Expert Zone

1

The path-swap requires exactly one redirect per pointer. A second redirect breaks distance symmetry — pA would travel lenA + 2×lenB and pB would travel lenB + 2×lenA, which are only equal when lenA == lenB, destroying the general solution.

2

If both lists are the same length, the pointers stay synchronized from step one and find the intersection (or reach NULL together) without any redirect.

3

In C, NULL is implementation-defined as 0 or (void*)0. All null pointers compare equal regardless of type, so pA == pB terminating when both are NULL is guaranteed by the C standard.

When NOT to use

If lists may contain cycles, pointers never reach NULL so the redirect never fires and the loop runs forever — detect and break cycles first. If using function pointers or complex struct hierarchies, ensure the same struct type is being compared to avoid strict aliasing violations.

Production Patterns

In C systems code, pointer intersection detection is used in memory allocator debugging (detecting aliased free-list nodes), kernel linked list traversal (Linux kernel list_head structures), and static analysis tools that track pointer provenance. The path-swap principle generalizes to any two-sequence synchronization where a shared suffix must be located without dynamic allocation.

Connections

Floyd's Cycle Detection in C

Both use two-pointer synchronization with mathematically guaranteed convergence, operating purely on raw pointer comparisons.

Mastering intersection detection makes Floyd's algorithm intuitive — both problems reduce to: move two pointers with specific rules and they will meet at a meaningful address.

C Pointer Arithmetic and uintptr_t

The hash set approach requires converting pointers to integers — uintptr_t is the correct type for portable pointer hashing in C.

Knowing when to cast to uintptr_t vs when to compare pointers directly is a key C skill that prevents subtle platform-dependent bugs.

Linux Kernel list_head

The kernel's intrusive linked list uses embedded list_head structs where pointer identity determines node membership — the same identity-vs-value distinction central to this problem.

Understanding pointer identity at this level is the prerequisite for reading and contributing to kernel data structure code.

Common Pitfalls

#1 Comparing field values instead of pointer addresses.

Wrong approach:

while (pA && pB) {
if (pA->val == pB->val) /* WRONG — compares data */
return pA;
pA = pA->next;
pB = pB->next;
}

Correct approach:

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

Root cause:

In C, == on pointers compares addresses. == on int fields compares values. Using field comparison for intersection detection is semantically wrong and produces false positives.

#2 Advancing past NULL before redirecting, skipping the first node of the other list.

Wrong approach:

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

Correct approach:

pA = (pA != NULL) ? pA->next : headB;
/* Redirect is part of the advance expression */

Root cause:

Separating the NULL check from the advance skips headB's first node, breaking distance symmetry by one step and causing the algorithm to miss the intersection.

#3 Dereferencing pA in the loop condition causing undefined behavior when pA is NULL.

Wrong approach:

while (*pA != *pB) { /* UB when pA or pB is NULL */
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}

Correct approach:

while (pA != pB) { /* Safe — compares pointer values, no dereference */
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;

Root cause:

Dereferencing a NULL pointer is undefined behavior in C. The loop condition must compare pointers directly, not the data they point to.

Key Takeaways

Intersection means the same memory address (pA == pB in C) — never compare field values (pA->val == pB->val) for intersection detection.

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

NULL == NULL is guaranteed in C — both pointers reaching NULL simultaneously terminates the loop cleanly when no intersection exists.

Cast to uintptr_t (not int or long) when storing pointers as hash table keys in C — it is the only portable integer type guaranteed to hold a pointer without truncation.

Exactly one redirect per pointer is required — a second redirect breaks distance symmetry and produces wrong results.