Intersection Point of Two Linked Lists in DSA Rust

Mental Model

Two linked lists may share some nodes at the end. The intersection point is the first shared node. We find it by aligning their lengths and moving together.

Analogy: Imagine two roads merging into one highway. The intersection point is where both roads join and share the same path forward.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                      ↑
List B:       9 -> 4 -> 5 -> null
                      ↑
Intersection at node with value 4

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->4->5 (4 and 5 are shared nodes)

Goal: Find the node where both lists start to share nodes (value 4)

Step 1: Calculate lengths: lenA=5, lenB=3

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
List B: 9 -> 4 -> 5 -> null

Why: Knowing lengths helps align the lists to compare nodes at the same distance from end

Step 2: Advance pointer in longer list (A) by lenA - lenB = 2 steps

List A pointer at node 3 -> 4 -> 5 -> null
List B pointer at node 9 -> 4 -> 5 -> null

Why: Align both pointers so they have equal nodes left to traverse

Step 3: Move both pointers forward together until they meet

Pointers at nodes 3 and 9 (not equal)
Move to nodes 4 and 4 (equal)

Why: First node where pointers are equal is the intersection

Result:

Intersection node found at value 4
List A: 1 -> 2 -> 3 -> [4] -> 5 -> null
List B: 9 -> [4] -> 5 -> null

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct ListNode {
    val: i32,
    next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn get_length(head: &Option<Rc<RefCell<ListNode>>>) -> usize {
    let mut length = 0;
    let mut current = head.clone();
    while let Some(node) = current {
        length += 1;
        current = node.borrow().next.clone();
    }
    length
}

fn get_intersection_node(
    headA: Option<Rc<RefCell<ListNode>>>,
    headB: Option<Rc<RefCell<ListNode>>>,
) -> Option<Rc<RefCell<ListNode>>> {
    let lenA = get_length(&headA);
    let lenB = get_length(&headB);

    let mut currA = headA;
    let mut currB = headB;

    // Advance the longer list's pointer by the difference in lengths
    if lenA > lenB {
        for _ in 0..(lenA - lenB) {
            if let Some(node) = currA.clone() {
                currA = node.borrow().next.clone();
            }
        }
    } else {
        for _ in 0..(lenB - lenA) {
            if let Some(node) = currB.clone() {
                currB = node.borrow().next.clone();
            }
        }
    }

    // Move both pointers until they meet or reach the end
    while currA.is_some() && currB.is_some() {
        if Rc::ptr_eq(currA.as_ref().unwrap(), currB.as_ref().unwrap()) {
            return currA;
        }
        currA = currA.unwrap().borrow().next.clone();
        currB = currB.unwrap().borrow().next.clone();
    }

    None
}

fn print_list(head: &Option<Rc<RefCell<ListNode>>>) {
    let mut current = head.clone();
    while let Some(node) = current {
        print!("{} -> ", node.borrow().val);
        current = node.borrow().next.clone();
    }
    println!("null");
}

fn main() {
    // Shared nodes
    let node4 = ListNode::new(4);
    let node5 = ListNode::new(5);
    node4.borrow_mut().next = Some(node5.clone());

    // List A: 1 -> 2 -> 3 -> 4 -> 5
    let node1 = ListNode::new(1);
    let node2 = ListNode::new(2);
    let node3 = ListNode::new(3);
    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = Some(node4.clone());

    // List B: 9 -> 4 -> 5
    let node9 = ListNode::new(9);
    node9.borrow_mut().next = Some(node4.clone());

    println!("List A:");
    print_list(&Some(node1.clone()));
    println!("List B:");
    print_list(&Some(node9.clone()));

    let intersection = get_intersection_node(Some(node1), Some(node9));
    match intersection {
        Some(node) => println!("Intersection at node with value: {}", node.borrow().val),
        None => println!("No intersection found"),
    }
}

let lenA = get_length(&headA); let lenB = get_length(&headB);

Calculate lengths of both lists to find difference

if lenA > lenB { for _ in 0..(lenA - lenB) { if let Some(node) = currA.clone() { currA = node.borrow().next.clone(); } } } else { for _ in 0..(lenB - lenA) { if let Some(node) = currB.clone() { currB = node.borrow().next.clone(); } } }

Advance pointer in longer list by length difference to align both lists

while currA.is_some() && currB.is_some() { if Rc::ptr_eq(currA.as_ref().unwrap(), currB.as_ref().unwrap()) { return currA; } currA = currA.unwrap().borrow().next.clone(); currB = currB.unwrap().borrow().next.clone(); }

Move both pointers forward together until they meet or reach end

Output

List A:

1 -> 2 -> 3 -> 4 -> 5 -> null

List B:

9 -> 4 -> 5 -> null

Intersection at node with value: 4

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only pointers and counters, no extra data structures

vs Alternative: Naive approach compares every node of one list with every node of the other, O(m*n), which is slower

Edge Cases

One or both lists are empty

Function returns None immediately as no intersection is possible

DSA Rust

while currA.is_some() && currB.is_some() {

Lists do not intersect

Pointers reach end without meeting, function returns None

DSA Rust

while currA.is_some() && currB.is_some() {

Intersection at head node (both lists are same)

Function returns head node immediately

DSA Rust

if Rc::ptr_eq(currA.as_ref().unwrap(), currB.as_ref().unwrap()) {

When to Use This Pattern

When you see two linked lists and need to find if they share nodes, use the length alignment pattern to find the intersection efficiently.

Common Mistakes

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare node pointers (references) to detect actual shared nodes, not just equal values

Mistake: Not aligning the longer list pointer before simultaneous traversal
Fix: Advance the longer list pointer by the difference in lengths before moving both pointers together

Summary

Finds the first shared node where two linked lists intersect.

Use when you need to detect if two linked lists merge and find the merge point.

Align the lists by length difference, then move pointers together to find intersection.

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