Intersection Point of Two Linked Lists in DSA Rust - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start at headA and headB

↓

Traverse both lists to find lengths

↓

Calculate length difference

↓

Advance longer list by difference

↓

Traverse both lists together

↓

Check if nodes are same

↓

Return node

↓

Repeat

↓

No intersection -> return None

Start from both heads, find lengths, align starts, then move together to find intersection node or None.

Execution Sample

DSA Rust

fn get_intersection_node(headA: Option<Box<Node>>, headB: Option<Box<Node>>) -> Option<Box<Node>> {
    // Steps: find lengths, align, traverse together
}

This code finds the node where two linked lists intersect or returns None if no intersection.

Execution Table

Step	Operation	Pointer Positions	Length Counts	Visual State
1	Initialize pointers at headA and headB	ptrA=headA(1), ptrB=headB(4)	lenA=0, lenB=0	ListA: 1 -> 2 -> 3 -> 6 -> 7 -> None ListB: 4 -> 5 -> 6 -> 7 -> None
2	Traverse listA to count length	ptrA moves from 1 to None	lenA=5, lenB=0	ListA unchanged
3	Traverse listB to count length	ptrB moves from 4 to None	lenA=5, lenB=4	ListB unchanged
4	Calculate length difference and reset pointers	ptrA=headA(1), ptrB=headB(4)	lenA=5, lenB=4	Lists unchanged
5	Advance ptrA by difference (1 step)	ptrA moves to 2, ptrB at 4	lenA=5, lenB=4	Lists unchanged
6	Traverse both pointers together, compare nodes	ptrA=2, ptrB=4	lenA=5, lenB=4	No match yet
7	Move both pointers forward	ptrA=3, ptrB=5	lenA=5, lenB=4	No match yet
8	Move both pointers forward	ptrA=6, ptrB=6	lenA=5, lenB=4	Nodes match - intersection found
9	Return intersection node (6)	ptrA=6, ptrB=6	lenA=5, lenB=4	Intersection at node with value 6

💡 Intersection found at node with value 6, traversal stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 8	Final
ptrA	headA(1)	None (end of listA)	None	node(2)	node(6)	node(6)
ptrB	headB(4)	headB(4)	None (end of listB)	node(4)	node(6)	node(6)
lenA	0	5	5	5	5	5
lenB	0	0	4	4	4	4

Key Moments - 3 Insights

Why do we advance the pointer of the longer list before traversing together?

Because the longer list has extra nodes at the start, advancing it aligns both pointers equally far from the end, as shown in step 5 of the execution_table.

Why do we compare nodes by reference, not by value?

Intersection means the exact same node object is shared, not just equal values. Step 8 shows nodes with value 6 are the same node, so intersection is found.

What happens if there is no intersection?

Both pointers will reach None at the same time after traversing together without matching nodes, then the function returns None (not shown here but implied after step 9).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, where is ptrA pointing?

A Node with value 1

B Node with value 2

C Node with value 4

D Node with value 6

💡 Hint

Check the 'Pointer Positions' column at step 5 in execution_table.

At which step do ptrA and ptrB first point to the same node?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for 'Nodes match' in the Visual State column in execution_table.

If listB was longer by 2 nodes instead of 1, what would change in the execution_table?

A ptrB would advance before traversal

B ptrA would advance by 2 steps before traversal

C ptrA and ptrB would start at the same node

D No pointer advancement needed

💡 Hint

Recall step 5 where the longer list pointer advances by the length difference.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Find lengths of both lists
- Advance pointer of longer list by length difference
- Traverse both lists together
- First common node is intersection
- Return None if no intersection

Full Transcript

To find the intersection point of two linked lists, we start by measuring the length of each list. Then, we move the pointer of the longer list forward by the difference in lengths to align both pointers equally far from the end. Next, we traverse both lists together, comparing nodes by reference. When the pointers point to the same node, we have found the intersection. If no intersection exists, both pointers reach the end (None) simultaneously, and we return None.

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