Intersection Point of Two Linked Lists in DSA Rust - Build from Scratch

Intersection Point of Two Linked Lists

📖 Scenario: Imagine two train tracks that merge into one track at some point. We want to find the exact point where the two tracks join. In programming, this is like finding the intersection point of two linked lists.

🎯 Goal: You will build a Rust program that creates two linked lists which intersect at a certain node. Then, you will write code to find and print the value at the intersection point.

📋 What You'll Learn

Create two linked lists with some shared nodes to simulate intersection

Use a helper variable to store the length of each list

Implement logic to find the intersection node by comparing nodes

Print the value of the intersection node or indicate if there is no intersection

💡 Why This Matters

🌍 Real World

Finding intersection points in linked lists is useful in memory management, detecting shared resources, and debugging pointer-related issues.

💼 Career

Understanding linked list intersections helps in software engineering roles that involve low-level data structures, debugging, and optimizing memory usage.

1

Create two intersecting linked lists

Create a struct called ListNode with a field val of type i32 and a field next of type Option. Then create two linked lists named list1 and list2 that intersect at a node with value 8. The first list should be 4 -> 1 -> 8 -> 4 -> 5, and the second list should be 5 -> 6 -> 1 -> 8 -> 4 -> 5, sharing the nodes starting from the node with value 8.

DSA Rust

# Define ListNode struct and create two intersecting linked lists
# Your code here

Hint

Start by defining the ListNode struct. Then create the shared tail nodes first. Use Option> for the next pointer. Finally, build list1 and list2 by linking to the shared nodes.

2

Calculate lengths of both linked lists

Create a function called length that takes a reference to an Option<Box<ListNode>> and returns the length as usize. Then create two variables len1 and len2 that store the lengths of list1 and list2 respectively by calling the length function.

DSA Rust

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

fn main() {
    // Shared part of the lists: 8 -> 4 -> 5
    let shared = Some(Box::new(ListNode {
        val: 8,
        next: Some(Box::new(ListNode {
            val: 4,
            next: Some(Box::new(ListNode {
                val: 5,
                next: None,
            })),
        })),
    }));

    // First list: 4 -> 1 -> shared
    let list1 = Some(Box::new(ListNode {
        val: 4,
        next: Some(Box::new(ListNode {
            val: 1,
            next: shared.clone(),
        })),
    }));

    // Second list: 5 -> 6 -> 1 -> shared
    let list2 = Some(Box::new(ListNode {
        val: 5,
        next: Some(Box::new(ListNode {
            val: 6,
            next: Some(Box::new(ListNode {
                val: 1,
                next: shared.clone(),
            })),
        })),
    }));

    // Create a function called length that returns the length of a linked list
    // Then create variables len1 and len2 to store lengths of list1 and list2
    // Your code here
}

Hint

Write a function length that uses a loop to count nodes until it reaches None. Then call this function for both lists and store the results in len1 and len2.

3

Find the intersection node

Write a function called get_intersection_node that takes two references to Option<Box<ListNode>> named headA and headB. Use the lengths len1 and len2 to advance the longer list's pointer so both lists have equal remaining length. Then move both pointers step-by-step until they point to the same node (by pointer equality). Return an Option<&ListNode> which is the intersection node or None if no intersection exists. Call this function with list1 and list2 and store the result in intersection.

DSA Rust

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

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

fn main() {
    // Shared part of the lists: 8 -> 4 -> 5
    let shared = Some(Box::new(ListNode {
        val: 8,
        next: Some(Box::new(ListNode {
            val: 4,
            next: Some(Box::new(ListNode {
                val: 5,
                next: None,
            })),
        })),
    }));

    // First list: 4 -> 1 -> shared
    let list1 = Some(Box::new(ListNode {
        val: 4,
        next: Some(Box::new(ListNode {
            val: 1,
            next: shared.clone(),
        })),
    }));

    // Second list: 5 -> 6 -> 1 -> shared
    let list2 = Some(Box::new(ListNode {
        val: 5,
        next: Some(Box::new(ListNode {
            val: 6,
            next: Some(Box::new(ListNode {
                val: 1,
                next: shared.clone(),
            })),
        })),
    }));

    let len1 = length(&list1);
    let len2 = length(&list2);

    // Write get_intersection_node function and call it with list1 and list2
    // Store the result in intersection
    // Your code here
}

Hint

Use pointer equality with std::ptr::eq to check if two nodes are the same. Advance the longer list's pointer by the difference in lengths. Then move both pointers together until they meet or reach the end.

4

Print the intersection node value

Write a match statement on the variable intersection. If it is Some(node), print "Intersection at node with value: {node.val}". If it is None, print "No intersection found".

DSA Rust

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

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

fn get_intersection_node(headA: &'a Option>, headB: &'a Option>, lenA: usize, lenB: usize) -> Option {
    let mut curA = headA.as_ref().map(|b| &**b);
    let mut curB = headB.as_ref().map(|b| &**b);

    let mut diff = if lenA > lenB { lenA - lenB } else { lenB - lenA };

    if lenA > lenB {
        while diff > 0 {
            if let Some(node) = curA {
                curA = node.next.as_ref().map(|b| &**b);
            }
            diff -= 1;
        }
    } else {
        while diff > 0 {
            if let Some(node) = curB {
                curB = node.next.as_ref().map(|b| &**b);
            }
            diff -= 1;
        }
    }

    while curA.is_some() && curB.is_some() {
        if std::ptr::eq(curA.unwrap(), curB.unwrap()) {
            return curA;
        }
        curA = curA.unwrap().next.as_ref().map(|b| &**b);
        curB = curB.unwrap().next.as_ref().map(|b| &**b);
    }
    None
}

fn main() {
    // Shared part of the lists: 8 -> 4 -> 5
    let shared = Some(Box::new(ListNode {
        val: 8,
        next: Some(Box::new(ListNode {
            val: 4,
            next: Some(Box::new(ListNode {
                val: 5,
                next: None,
            })),
        })),
    }));

    // First list: 4 -> 1 -> shared
    let list1 = Some(Box::new(ListNode {
        val: 4,
        next: Some(Box::new(ListNode {
            val: 1,
            next: shared.clone(),
        })),
    }));

    // Second list: 5 -> 6 -> 1 -> shared
    let list2 = Some(Box::new(ListNode {
        val: 5,
        next: Some(Box::new(ListNode {
            val: 6,
            next: Some(Box::new(ListNode {
                val: 1,
                next: shared.clone(),
            })),
        })),
    }));

    let len1 = length(&list1);
    let len2 = length(&list2);

    let intersection = get_intersection_node(&list1, &list2, len1, len2);

    // Use match to print the intersection node value or no intersection
    // Your code here
}

Hint

Use a match on intersection. If Some(node), print the node's value. Otherwise, print that no intersection was found.

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