Intersection Point of Two Linked Lists in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the intersection node value

Given two singly linked lists that intersect, what is the value of the node where they intersect?

DSA Rust

use std::rc::Rc;

struct ListNode {
    val: i32,
    next: Option<Rc<ListNode>>,
}

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

fn get_intersection_node_value(
    head_a: &Option<Rc<ListNode>>,
    head_b: &Option<Rc<ListNode>>,
) -> Option<i32> {
    use std::collections::HashSet;
    let mut nodes = HashSet::new();
    let mut current_a = head_a;
    while let Some(node) = current_a {
        nodes.insert(&**node as *const ListNode);
        current_a = &node.next;
    }
    let mut current_b = head_b;
    while let Some(node) = current_b {
        if nodes.contains(&**node as *const ListNode) {
            return Some(node.val);
        }
        current_b = &node.next;
    }
    None
}

fn main() {
    // Assume intersection node is shared
    let intersect = Rc::new(ListNode { val: 7, next: Some(Rc::new(ListNode { val: 9, next: None })) });

    let list_a = Some(Rc::new(ListNode {
        val: 1,
        next: Some(Rc::new(ListNode {
            val: 3,
            next: Some(Rc::new(ListNode {
                val: 5,
                next: Some(intersect.clone()),
            })),
        })),
    }));

    let list_b = Some(Rc::new(ListNode {
        val: 2,
        next: Some(Rc::new(ListNode {
            val: 4,
            next: Some(intersect.clone()),
        })),
    }));

    let result = get_intersection_node_value(&list_a, &list_b);
    println!("{}", result.unwrap_or(-1));
}

A -1

B 9

C 5

D 7

💡 Hint

Think about how to detect the first common node by comparing node addresses.

The intersection node is the first node shared by both lists, which has value 7.

🧠 Conceptual

intermediate

Why do two linked lists intersect at a node?

What is the main reason two singly linked lists can share an intersection node?

A They have nodes with the same value but different memory addresses.

B They share the same node object in memory after some point.

C They have the same length and values in all nodes.

D They are reversed versions of each other.

💡 Hint

Think about what it means for two lists to intersect physically, not just by value.

Two linked lists intersect if they share the exact same node object in memory from some point onward.

🔧 Debug

advanced

Identify the error in intersection detection code

What error will this Rust code produce when trying to find the intersection node of two linked lists?

DSA Rust

fn get_intersection_node(
    head_a: &Option<Box<ListNode>>,
    head_b: &Option<Box<ListNode>>,
) -> Option<i32> {
    let mut current_a = head_a;
    let mut current_b = head_b;
    while current_a.is_some() && current_b.is_some() {
        if current_a == current_b {
            return current_a.as_ref().map(|node| node.val);
        }
        current_a = &current_a.as_ref().unwrap().next;
        current_b = &current_b.as_ref().unwrap().next;
    }
    None
}

A The code will panic due to unwrap on None when lists have different lengths.

B The code causes infinite loop because pointers never advance.

C The code compares node values instead of node references, so it misses intersections.

D The code compiles and runs correctly, returning the intersection value.

💡 Hint

Check what happens when one list is longer than the other.

The code unwraps next without checking if it is None, causing panic if lists differ in length.

❓ Predict Output

advanced

Output of intersection detection with pointer alignment

What is the output of this Rust code that finds the intersection node by aligning list lengths?

DSA Rust

use std::rc::Rc;

struct ListNode {
    val: i32,
    next: Option<Rc<ListNode>>,
}

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

fn get_intersection_node(
    mut head_a: &Option<Rc<ListNode>>,
    mut head_b: &Option<Rc<ListNode>>,
) -> Option<i32> {
    let len_a = get_length(head_a);
    let len_b = get_length(head_b);

    let mut diff = if len_a > len_b { len_a - len_b } else { len_b - len_a };

    if len_a > len_b {
        while diff > 0 {
            head_a = &head_a.as_ref()?.next;
            diff -= 1;
        }
    } else {
        while diff > 0 {
            head_b = &head_b.as_ref()?.next;
            diff -= 1;
        }
    }

    while head_a.is_some() && head_b.is_some() {
        if std::ptr::eq(&**head_a.as_ref()?, &**head_b.as_ref()?) {
            return head_a.as_ref().map(|node| node.val);
        }
        head_a = &head_a.as_ref()?.next;
        head_b = &head_b.as_ref()?.next;
    }
    None
}

fn main() {
    let intersect = Rc::new(ListNode { val: 8, next: Some(Rc::new(ListNode { val: 10, next: None })) });

    let list_a = Some(Rc::new(ListNode {
        val: 3,
        next: Some(Rc::new(ListNode {
            val: 7,
            next: Some(intersect.clone()),
        })),
    }));

    let list_b = Some(Rc::new(ListNode {
        val: 99,
        next: Some(Rc::new(ListNode {
            val: 1,
            next: Some(intersect.clone()),
        })),
    }));

    let result = get_intersection_node(&list_a, &list_b);
    println!("{}", result.unwrap_or(-1));
}

A -1

B 10

C 8

D 99

💡 Hint

The intersection node is the first shared node after aligning list lengths.

The code aligns the longer list pointer to the same distance from the end, then compares nodes by pointer equality. The intersection node has value 8.

🚀 Application

expert

Calculate number of nodes after intersection

Given two intersecting singly linked lists, how many nodes are there from the intersection node to the end?

DSA Rust

use std::rc::Rc;

struct ListNode {
    val: i32,
    next: Option<Rc<ListNode>>,
}

fn count_nodes_from_intersection(
    head_a: &Option<Rc<ListNode>>,
    head_b: &Option<Rc<ListNode>>,
) -> usize {
    use std::collections::HashSet;
    let mut nodes = HashSet::new();
    let mut current_a = head_a;
    while let Some(node) = current_a {
        nodes.insert(&**node as *const ListNode);
        current_a = &node.next;
    }
    let mut current_b = head_b;
    while let Some(node) = current_b {
        if nodes.contains(&**node as *const ListNode) {
            // Count nodes from intersection to end
            let mut count = 0;
            let mut temp: Option<&ListNode> = Some(&**node);
            while let Some(n) = temp {
                count += 1;
                temp = n.next.as_ref().map(|b| &**b);
            }
            return count;
        }
        current_b = &node.next;
    }
    0
}

fn main() {
    let intersect = Rc::new(ListNode { val: 15, next: Some(Rc::new(ListNode { val: 30, next: None })) });

    let list_a = Some(Rc::new(ListNode {
        val: 10,
        next: Some(Rc::new(ListNode {
            val: 12,
            next: Some(intersect.clone()),
        })),
    }));

    let list_b = Some(Rc::new(ListNode {
        val: 3,
        next: Some(Rc::new(ListNode {
            val: 6,
            next: Some(Rc::new(ListNode {
                val: 9,
                next: Some(intersect.clone()),
            })),
        })),
    }));

    let result = count_nodes_from_intersection(&list_a, &list_b);
    println!("{}", result);
}

A 2

B 3

C 4

D 5

💡 Hint

Count nodes starting from the intersection node to the end of the list.

The intersection node is 15, followed by 30, so total 2 nodes from intersection to end.

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