Remove Nth Node from End of List in DSA Rust - Execution Trace

Concept Flow - Remove Nth Node from End of List

Start with head node

↓

Set two pointers: fast and slow at head

↓

Move fast pointer n steps ahead

↓

Move both pointers forward until fast reaches end

↓

Slow pointer now at node before target

↓

Change slow.next to skip target node

↓

Return modified list head

We use two pointers to find the node before the one to remove, then skip it to remove from the list.

Execution Sample

DSA Rust

fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
    let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
    let mut fast = &dummy;
    let mut slow = &mut dummy;
    for _ in 0..n {
        fast = &fast.as_ref().unwrap().next;
    }
    while fast.as_ref().unwrap().next.is_some() {
        fast = &fast.as_ref().unwrap().next;
        slow = &mut slow.as_mut().unwrap().next;
    }
    let next = slow.as_mut().unwrap().next.take();
    slow.as_mut().unwrap().next = next.unwrap().next;
    dummy.unwrap().next
}

This Rust function removes the nth node from the end of a singly linked list using two pointers.

Execution Table

Step	Operation	Fast Pointer Position	Slow Pointer Position	Pointer Changes	Visual State
1	Initialize dummy node pointing to head	dummy -> head	dummy -> head	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move fast pointer 1 step ahead (n=1)	points to node 1	dummy	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move fast and slow pointers forward until fast reaches end	node 2	node 0 (dummy)	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
4	Move fast and slow pointers forward	node 3	node 1	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
5	Move fast and slow pointers forward	node 4	node 2	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
6	Move fast and slow pointers forward	node 5	node 3	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
7	Move fast and slow pointers forward	null (end)	node 4	None	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
8	Remove node after slow (node 5)	null	node 4	slow.next = node 5.next (null)	0 -> 1 -> 2 -> 3 -> 4 -> null
9	Return list starting after dummy	null	null	None	1 -> 2 -> 3 -> 4 -> null
10	End	null	null	None	1 -> 2 -> 3 -> 4 -> null

💡 fast pointer reached end (null), slow pointer at node before target, removal done

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 8	Final
fast pointer	dummy	node 1	null	null	null
slow pointer	dummy	dummy	node 4	node 4	null
list state	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	0 -> 1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null

Key Moments - 3 Insights

Why do we move the fast pointer n steps ahead before moving slow?

Moving fast pointer n steps ahead creates a gap so when fast reaches the end, slow is right before the node to remove (see steps 2 and 7 in execution_table).

Why do we use a dummy node at the start?

Dummy node helps handle edge cases like removing the first node by providing a stable node before head (step 1).

What happens if n equals the length of the list?

Slow pointer stays at dummy, so removing slow.next removes the head node (step 8).

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after step 7?

A node 4

B node 5

C dummy node

D node 3

💡 Hint

Check the 'Slow Pointer Position' column at step 7 in execution_table.

At which step does the fast pointer reach the end of the list?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'Fast Pointer Position' column to find when it becomes null.

If n was 2 instead of 1, how would the slow pointer position change at step 7?

A It would be at node 2

B It would be at node 4

C It would be at node 3

D It would be at dummy node

💡 Hint

Increasing n moves fast pointer further ahead, so slow pointer stops earlier (compare variable_tracker for slow pointer).

Concept Snapshot

Remove Nth Node from End of List:
- Use two pointers: fast and slow
- Move fast n steps ahead
- Move both until fast reaches end
- Slow points before target node
- Change slow.next to skip target
- Use dummy node to handle head removal

Full Transcript

This concept shows how to remove the nth node from the end of a singly linked list using two pointers. First, a dummy node is created before the head to simplify edge cases. The fast pointer moves n steps ahead, creating a gap. Then both fast and slow pointers move forward together until fast reaches the end. At this point, slow points to the node before the one to remove. We then change slow's next pointer to skip the target node, effectively removing it. Finally, the list starting after the dummy node is returned. This method handles all cases including removing the head node.

Practice

1. What does the problem Remove Nth Node from End of List ask you to do?

easy

A. Reverse the linked list up to the nth node

B. Add a new node at the nth position from the start

C. Delete the node that is the nth from the end in a linked list

D. Find the value of the nth node from the start

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is nth from the end in a singly linked list.

2. Step 2: Clarify the operation

   We do not add or reverse nodes; we specifically delete the nth node counting from the list's end.

3. Final Answer:

   Delete the node that is the nth from the end in a linked list -> Option C

4. Quick Check:

   Remove nth from end = Delete nth from end [OK]

Hint: Focus on 'remove nth from end' means delete that node [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Thinking the problem is about reversing the list
• Assuming insertion instead of deletion

2. Which Rust code snippet correctly declares a singly linked list node struct for this problem?

easy

A. struct ListNode { val: i32, next: &ListNode }

B. struct ListNode { val: i32, next: Option }

C. struct ListNode { val: i32, next: Box<ListNode> }

D. struct ListNode { val: i32, next: Option<&ListNode> }

Solution

1. Step 1: Recall Rust ownership for linked lists

   Rust uses Option to allow nullable next pointers with ownership.

2. Step 2: Check each option

   struct ListNode { val: i32, next: Option } uses Option which is correct. Options A and D use references without ownership, which is unsafe. struct ListNode { val: i32, next: Box<ListNode> } lacks Option, so no null end.

3. Final Answer:

   struct ListNode { val: i32, next: Option } -> Option B

4. Quick Check:

   Rust linked list node = Option [OK]

Hint: Use Option for nullable owned pointers in Rust [OK]

Common Mistakes:

• Using references (&) instead of Box for next
• Omitting Option causing no null end
• Forgetting ownership rules in Rust

3. Given the Rust code below, what is the linked list output after removing the 2nd node from the end?

let mut list = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 3, next: None })) })) }));
// Remove 2nd from end
let result = remove_nth_from_end(list, 2);
// Print list values

medium

A. 1 -> 2 -> 3 -> null

B. 1 -> 2 -> null

C. 2 -> 3 -> null

D. 1 -> 3 -> null

Solution

1. Step 1: Identify the list and node to remove

   The list is 1 -> 2 -> 3. Removing 2nd from end means removing node with value 2.

2. Step 2: Remove the node and update links

   After removal, list becomes 1 -> 3 -> null.

3. Final Answer:

   1 -> 3 -> null -> Option D

4. Quick Check:

   Remove 2nd from end removes '2' [OK]

Hint: Count from end, remove that node, link neighbors [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Not updating next pointers correctly
• Confusing 2nd from end with 2nd from start

4. The following Rust function aims to remove the nth node from the end but has a bug. What is the bug?

fn remove_nth_from_end(head: Option, n: i32) -> Option {
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut first = &dummy;
    let mut second = &mut dummy;
    for _ in 0..n {
        first = first.next.as_ref().unwrap();
    }
    while first.next.is_some() {
        first = first.next.as_ref().unwrap();
        second = second.next.as_mut().unwrap();
    }
    second.next = second.next.as_mut().unwrap().next.take();
    dummy.next
}

medium

A. Using unwrap() without checking may panic if list is short

B. second is immutable, cannot modify next pointer

C. first is an immutable reference, cannot advance correctly

D. dummy.next is returned before modification

Solution

1. Step 1: Analyze unwrap usage

   The code uses unwrap() on next without checking if next exists, which can panic if n is larger than list length.

2. Step 2: Confirm other references are valid

   first is immutable reference but used only for reading, second is mutable for modification, dummy.next returned after modification.

3. Final Answer:

   Using unwrap() without checking may panic if list is short -> Option A

4. Quick Check:

   unwrap() without safety check causes panic [OK]

Hint: Check unwrap() calls for possible panics [OK]

Common Mistakes:

• Confusing mutable and immutable references
• Ignoring unwrap panic risks
• Assuming dummy.next is returned too early

5. You want to remove the nth node from the end of a linked list in Rust. Which approach correctly handles the edge case when the node to remove is the head node?

hard

A. Use a dummy node before head and adjust dummy.next after removal

B. Directly remove head without dummy node by shifting head pointer

C. Traverse twice: first to count length, second to remove node without dummy

D. Convert list to vector, remove element, then rebuild list

Solution

1. Step 1: Understand the edge case

   If the node to remove is the head, removing it directly is tricky because head pointer must change.

2. Step 2: Use dummy node technique

   Adding a dummy node before head simplifies removal by always having a previous node to update, including when head is removed.

3. Final Answer:

   Use a dummy node before head and adjust dummy.next after removal -> Option A

4. Quick Check:

   Dummy node handles head removal edge case [OK]

Hint: Add dummy node to simplify head removal [OK]

Common Mistakes:

• Not handling head removal separately
• Forgetting to update head pointer
• Using inefficient vector conversion