Intersection Point of Two Linked Lists in DSA Rust - 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. In Rust, linked lists using raw pointers or Rc> make pointer identity explicit. Intersection means two pointers hold the same memory address — checked with Rc::ptr_eq() for Rc-based nodes or direct raw pointer comparison.

Why it matters

Rust's ownership model makes traditional linked list intersection detection an important exercise in understanding Rc>, raw pointers, and shared ownership. The two-pointer path-swap technique demonstrates how to reason about pointer identity in Rust's strict ownership system.

Where it fits

You need comfort with Rust's Rc>, Option>>, and shared ownership before tackling this. After mastering it, Floyd's cycle detection and merge sort on linked lists follow as key applications.

Mental Model

Core Idea

Two runners covering the same total distance by switching paths will meet exactly at the shared section — regardless of which path they started on.

Think of it like...

Two rivers of different lengths merge into one. A boat taking river A then river B, and another taking B then A, both travel the same total distance and enter the merged river simultaneously.

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

pA: 1→3→5→8→10→None → 2→4→[8] ✓
pB: 2→4→8→10→None → 1→3→5→[8] ✓
Both reach the same Rc<RefCell<ListNode>>{val:8}.

Build-Up - 6 Steps

1

Foundation

Pointer Identity in Rust — Rc::ptr_eq()

Concept: Rc::ptr_eq(a, b) returns true only when both Rc pointers point to the same allocation.

In Rust, Rc is a reference-counted pointer. Two Rc values can hold the same data (equal values) but be different allocations. Rc::ptr_eq(&a, &b) checks whether both point to the exact same heap allocation — this is the intersection check. Comparing values with == would require PartialEq on the node type and would give false positives on duplicate values.

Result

Rc::ptr_eq() is the correct intersection check — it compares pointer addresses, not node values.

Rust makes pointer identity explicit through Rc::ptr_eq() rather than implicit == overloading. This clarity is a feature — it prevents accidental value-based comparison.

2

Foundation

Shared Ownership — Why Rc is Needed for Intersection

Concept: Rust's ownership rules require Rc> for nodes shared between two lists.

In Rust, a value can have only one owner. A node in the shared tail is owned by BOTH lists — this violates single ownership. Rc (Reference Counted) enables shared ownership by keeping a reference count. When two lists share a tail, the shared nodes are wrapped in Rc>, allowing both list heads to hold references to the same allocation safely.

Result

Shared tail nodes must use Rc> — the standard Rust approach to shared mutable data.

The need for Rc here reveals the fundamental challenge: Rust's ownership model makes intersection a language design question, not just an algorithm question.

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: Count lengths, advance the longer pointer by the difference, then walk both in sync.

Traverse both lists to get lenA and lenB. If lenA > lenB, advance pA by (lenA - lenB) steps. Both are now equidistant from None. Walk both one step per iteration. First node where Rc::ptr_eq(&pA, &pB) is true 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 None, the first common Rc allocation must be the intersection.

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 node count? Commit yes or no.

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

Initialize pA = clone of headA (Rc::clone for shared reference), pB = clone of headB. Each step advance both. When pA is None, set pA = headB.clone(). When pB is None, set pB = headA.clone(). Continue until Rc::ptr_eq or both are None. Both traverse lenA + lenB nodes total.

Result

Elegant O(m+n) time, O(1) extra space (Rc::clone is O(1) — just increments refcount).

Rc::clone() does not copy data — it only increments the reference count. The path-swap in Rust is efficient and safe.

5

Advanced

None == None Termination

🤔Before reading on: when both pointers become None simultaneously in Rust, does the loop terminate correctly? Commit yes or no.

Concept: When no intersection exists, both Option pointers become None at the same step, terminating the loop.

If no intersection exists, pA and pB both become None after traversing both lists. Option::None == Option::None is true in Rust. The loop condition — checking both are not the same Rc or both are None — exits cleanly. Return None to indicate no intersection.

Result

Same loop handles both intersecting and non-intersecting cases.

Rust's Option::None is always equal to Option::None — the termination condition is guaranteed.

6

Expert

HashSet with Rc Raw Pointers

🤔Before reading on: can you use a HashSet<*const ListNode> to track visited raw pointer addresses from list A? Commit yes or no.

Concept: Store raw Rc pointer addresses in a HashSet for O(1) lookup.

In Rust, Rc::as_ptr() returns the raw *const T pointer to the allocation. A HashSet<*const ListNode> can store these addresses. Traverse list A: visited.insert(Rc::as_ptr(&node)). Traverse list B: check visited.contains(&Rc::as_ptr(&node)). Time O(m+n), space O(m). This requires unsafe-free Rc::as_ptr() available in stable Rust.

Result

Correct O(m+n) solution at O(m) space — simpler to implement than the two-pointer approach.

Rc::as_ptr() extracts the raw address without unsafe code. This is the idiomatic Rust way to get a pointer identity for hashing.

Under the Hood

The path-swap works because pA travels lenA + lenB nodes and pB travels lenB + lenA — identical totals. If intersection exists at distance d from None, both arrive at that Rc allocation after lenA + lenB - d steps. Rc::clone() is O(1) — just a refcount increment. Rc::ptr_eq() compares the raw pointer addresses stored inside the Rc fat pointers.

Why designed this way?

Rust's Rc> for linked lists reflects the ownership challenge: shared tails require shared ownership. The algorithm itself is language-agnostic, but the implementation must respect Rust's ownership rules by using Rc::clone() for shared references and Rc::ptr_eq() for identity comparison.

Rc<RefCell<ListNode>> fat pointer structure:
  [ptr → heap allocation | refcount]

Rc::ptr_eq(a, b) compares the 'ptr' field:
  Same heap address → true (intersection)
  Different addresses → false (different nodes)

pA after path-swap meets pB at the shared Rc allocation.

Myth Busters - 3 Common Misconceptions

Quick: does == on two Rc> check pointer identity in Rust? Commit yes or no.

Common Belief: == on Rc> checks if they point to the same allocation.

Reality: == on Rc compares the inner T values (if T: PartialEq), not the pointer addresses. Use Rc::ptr_eq() for address comparison.

Why it matters: Using == instead of Rc::ptr_eq() gives false positives on nodes with equal values — a silent correctness bug.

Quick: does Rc::clone() copy the heap data? Commit yes or no.

Common Belief: Rc::clone() copies the entire node data.

Reality: Rc::clone() only increments the reference count — O(1) operation. The heap data is shared, not copied.

Why it matters: Thinking Rc::clone() is expensive leads to unnecessary avoidance of the standard shared ownership pattern in Rust.

Quick: is Rc thread-safe in Rust? Commit yes or no.

Common Belief: Rc can be shared across threads safely.

Reality: Rc is NOT thread-safe — it uses non-atomic reference counting. For multi-threaded shared ownership, use Arc (Atomic Reference Counted).

Why it matters: Using Rc across thread boundaries is a compile error in Rust — the compiler enforces this. Use Arc> for concurrent linked list problems.

Expert Zone

1

The path-swap requires exactly one redirect per pointer. Using Rc::clone() for the redirect is correct — it shares the same allocation, not a copy.

2

In competitive programming, Rust linked lists often use Vec with index-based 'pointers' to avoid Rc overhead. The intersection algorithm still works — compare indices instead of Rc pointers.

3

Rc::ptr_eq() is available in stable Rust since 1.17. For raw pointers (*const T), use std::ptr::eq() for the same address comparison.

When NOT to use

If the problem requires thread-safety, use Arc::ptr_eq() instead of Rc::ptr_eq(). If using index-based linked list representation (common in competitive Rust), compare indices directly instead of pointer addresses.

Production Patterns

Rc::ptr_eq() appears in Rust's own standard library for detecting aliased Rc pointers. Arc::ptr_eq() is used in concurrent reference-counted data structures. Both functions express the same concept: identity equality vs value equality.

Connections

Rust Ownership and Rc<T>

The need for Rc in shared-tail linked lists directly illustrates Rust's ownership model — single ownership cannot handle shared structure without reference counting.

This problem is a microcosm of Rust's approach to shared mutable data: Rc for single-threaded, Arc for multi-threaded, both with ptr_eq() for identity.

Floyd's Cycle Detection in Rust

Both use two-pointer techniques on Rc-based linked lists, requiring Rc::clone() for pointer manipulation and Rc::ptr_eq() for meeting detection.

Mastering Rc::ptr_eq() here makes Floyd's algorithm in Rust straightforward — same ownership patterns, same identity comparison.

Common Pitfalls

#1 Using == instead of Rc::ptr_eq() for intersection detection.

Wrong approach:

if pA == pB { // WRONG — compares values if PartialEq implemented
return Some(pA);
}

Correct approach:

if Rc::ptr_eq(&pA, &pB) { // Correct — compares pointer addresses
return Some(pA);
}

Root cause:

== on Rc delegates to T's PartialEq, comparing values not addresses. Rc::ptr_eq() is the explicit address comparison function.

#2 Forgetting to Rc::clone() when redirecting — moving instead of sharing.

Wrong approach:

if pA.is_none() {
pA = head_b; // WRONG — moves head_b, making it unusable
}

Correct approach:

if pA.is_none() {
pA = head_b.clone(); // Correct — Rc::clone increments refcount, shares allocation
}

Root cause:

In Rust, assignment moves ownership. Using head_b directly would move it into pA, invalidating head_b for future redirects. Rc::clone() creates a new shared reference.

Key Takeaways

Use Rc::ptr_eq(&a, &b) for intersection detection in Rust — not == which compares values.

Rc::clone() is O(1) — it only increments the reference count, not copies data. Safe and efficient for path-swap redirects.

Shared tail nodes require Rc> in Rust — single ownership cannot model shared structure.

Rc::as_ptr() extracts the raw address for HashSet-based visited tracking — works without unsafe code.

Rc is not thread-safe — use Arc::ptr_eq() for concurrent linked list problems.

Practice

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

easy

A. The last node of the shorter linked list.

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

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

D. The first node of the longer 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 C

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 start

2. Which Rust code snippet correctly declares a singly linked list node struct for intersection detection?

easy

A. struct Node { value: i32, next: Option }

B. struct Node { value: i32, next: Node }

C. struct Node { value: i32, next: &Node }

D. struct Node { value: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust linked list node

   Rust needs Option<Box<Node>> for next to allow None and heap allocation.

2. Step 2: Check each option

   A uses raw Node causing infinite size error. C uses reference without lifetime. D lacks Option so cannot represent end of list. The correct declaration uses Option<Box<Node>>.

3. Final Answer:

   struct Node { value: i32, next: Option<Box<Node>> } -> Option A

4. Quick Check:

   Use Option<Box<Node>> for next pointer [OK]

Hint: Use Option<Box<Node>> for next to allow null and heap storage [OK]

Common Mistakes:

• Omitting Option causing infinite size error
• Using references without lifetimes
• Using raw Node type causing recursive size

3. Given two linked lists in Rust where list A is 1 -> 2 -> 3 -> 4 -> 5 and list B is 9 -> 4 -> 5, assuming nodes with values 4 and 5 are shared (intersection), what is the intersection point value?

medium

A. 4

B. 5

C. 3

D. 9

Solution

1. Step 1: Identify shared nodes

   Lists share nodes with values 4 and 5, meaning intersection starts at node with value 4.

2. Step 2: Determine intersection point

   The first shared node is the intersection point, which is value 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   First shared node value = 4 [OK]

Hint: Intersection is first shared node, not last [OK]

Common Mistakes:

• Choosing last shared node value
• Picking non-shared node values
• Confusing node value with node reference

4. Consider this Rust function snippet to find intersection point of two linked lists:

fn get_intersection_node(head_a: Option<&Box<Node>>, head_b: Option<&Box<Node>>) -> Option<&Box<Node>> {
    let mut a = head_a;
    let mut b = head_b;
    while a != b {
        a = if let Some(node) = a { node.next.as_ref() } else { head_b };
        b = if let Some(node) = b { node.next.as_ref() } else { head_a };
    }
    a
}

What is the main bug in this code?

medium

A. It does not handle None cases properly causing infinite loop.

B. It compares node references incorrectly using != instead of pointer equality.

C. It assigns head_b and head_a inside loop incorrectly causing logic error.

D. It uses references without proper lifetime annotations causing compile error.

Solution

1. Step 1: Analyze compilation

   The function uses bare references (&Box<Node>) in Option without lifetime parameters.

2. Step 2: Rust lifetime rules

   Explicit lifetime annotations are required (e.g., fn<'a>(head_a: Option<&'a Box<Node>>, ...) -> Option<&'a Box<Node>>), otherwise it fails to compile due to unresolved lifetimes.

3. Final Answer:

   It uses references without proper lifetime annotations causing compile error. -> Option D

4. Quick Check:

   Missing lifetime specifiers [OK]

Hint: Rust linked list functions need lifetime annotations for node references [OK]

Common Mistakes:

• Assuming != compares pointers correctly
• Ignoring infinite loop possibility
• Overlooking lifetime errors

5. You have two singly linked lists that intersect. List A length is 7, List B length is 5. To find the intersection point efficiently, which approach is best?

hard

A. Traverse both lists fully and store nodes in hash sets to find intersection.

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

C. Reverse both lists and compare nodes from start until mismatch.

D. Compare values of nodes one by one from heads until match found.

Solution

1. Step 1: Understand length difference method

   Calculate difference in lengths (7 - 5 = 2), advance longer list by 2 nodes to align both lists.

2. Step 2: Move both pointers together

   Then move both pointers one step at a time until they point to the same node (intersection point).

3. Final Answer:

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

4. Quick Check:

   Align lists by length difference for efficient intersection [OK]

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

Common Mistakes:

• Using extra memory unnecessarily
• Reversing lists which is inefficient
• Comparing node values instead of references