Intersection Point of Two Linked Lists in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the intersection point of two linked lists?

It is the node where two linked lists merge and share the same next nodes onwards.

beginner

Why can't we just compare node values to find the intersection point?

Because nodes can have the same value but be different nodes. Intersection means the exact same node in memory.

intermediate

What is the main idea behind the two-pointer approach to find the intersection?

Use two pointers starting at each list head. When one reaches the end, switch it to the other list's head. They meet at intersection or end.

intermediate

What is the time complexity of the two-pointer method for intersection detection?

O(m + n), where m and n are the lengths of the two linked lists.

intermediate

In Rust, why do we use Option and Rc for linked list nodes?

Option allows for None (end of list). Rc enables multiple ownership needed for shared nodes in intersection.

What does the intersection point of two linked lists represent?

A The node where both lists share the same memory address

B The node with the same value in both lists

C The first node of the longer list

D The last node of the shorter list

Intersection means the exact same node in memory, not just same value.

In the two-pointer approach, what happens when a pointer reaches the end of its list?

A It stops moving

B It switches to the head of the other list

C It moves backwards

D It resets to the start of the same list

Switching pointers ensures both traverse equal total length.

What is the main benefit of using the two-pointer method over brute force?

A Runs in linear time without extra space

B Uses less memory

C Finds intersection faster by skipping nodes

D Works only for sorted lists

Two-pointer method runs in O(m+n) time and O(1) space.

Why do we need shared ownership (Rc) in Rust for intersection nodes?

A To prevent memory leaks

B To make nodes mutable

C To allow multiple lists to own the same node

D To speed up traversal

Rc allows multiple owners of the same node, needed for intersection.

If two linked lists do not intersect, what will the two-pointer method return?

A The last node of the longer list

B The first node of the shorter list

C The head of the first list

D None (no intersection)

If no intersection, pointers will both reach None at the same time.

Explain how the two-pointer technique finds the intersection point of two linked lists.

Think about equalizing path lengths by switching heads.

Describe why shared ownership (Rc) is necessary in Rust when implementing linked lists with intersection.

Consider how two lists can point to the same node.

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