Remove Nth Node from End of List in DSA Rust

Mental Model

We want to remove a node counting from the end, so we use two pointers spaced apart to find it in one pass.

Analogy: Imagine two friends walking on a path; one starts ahead by n steps. When the front friend reaches the end, the back friend is exactly at the node before the one to remove.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑         ↑
         slow      fast

Dry Run Walkthrough

Input: list: 1->2->3->4->5, remove 2nd node from end

Goal: Remove the 2nd node from the end, which is node with value 4

Step 1: Move fast pointer 2 steps ahead

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑                   ↑
         slow                fast

Why: We move fast pointer n steps ahead to create a gap of n between slow and fast

Step 2: Move both slow and fast pointers one step forward

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
               ↑         ↑
              slow      fast

Why: Moving both pointers keeps the gap and moves slow closer to the node before the target

Step 3: Move both slow and fast pointers one step forward again

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                    ↑    ↑
                   slow fast

Why: Slow is now just before the node to remove (4)

Step 4: Fast pointer moves to null (end), slow pointer is before target

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                         ↑
                        slow

Why: Fast reached end, slow is at node before the one to remove

Step 5: Remove node after slow by linking slow to node after next

head -> 1 -> 2 -> 3 -> 5 -> null

Why: By skipping node 4, we remove it from the list

Result:

head -> 1 -> 2 -> 3 -> 5 -> null

Annotated Code

DSA Rust

use std::option::Option;

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

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut slow: *mut Box<ListNode> = &mut dummy;
    let mut fast: *mut Box<ListNode> = &mut dummy;

    // Move fast pointer n steps ahead
    for _ in 0..n {
        unsafe {
            fast = match (*fast).next.as_mut() {
                Some(node) => node,
                None => return dummy.next,
            };
        }
    }

    // Move both pointers until fast reaches the end
    unsafe {
        while let Some(next_node) = (*fast).next.as_mut() {
            fast = next_node;
            slow = match (*slow).next.as_mut() {
                Some(node) => node,
                None => break,
            };
        }

        // Remove the nth node from end
        let node_to_remove = (*slow).next.take();
        if let Some(mut node) = node_to_remove {
            (*slow).next = node.next.take();
        }
    }

    dummy.next
}

fn print_list(head: &Option<Box<ListNode>>) {
    let mut curr = head.as_ref();
    while let Some(node) = curr {
        print!("{} -> ", node.val);
        curr = node.next.as_ref();
    }
    println!("null");
}

fn main() {
    // Create list 1->2->3->4->5->null
    let mut head = Some(Box::new(ListNode::new(1)));
    let mut curr = head.as_mut();
    for val in 2..=5 {
        if let Some(node) = curr {
            node.next = Some(Box::new(ListNode::new(val)));
            curr = node.next.as_mut();
        }
    }

    println!("Original list:");
    print_list(&head);

    let n = 2;
    let new_head = remove_nth_from_end(head, n);

    println!("List after removing {}th node from end:", n);
    print_list(&new_head);
}

for _ in 0..n { unsafe { fast = match (*fast).next.as_mut() { Some(node) => node, None => return dummy.next, }; } }

Advance fast pointer n steps ahead to create gap

while let Some(next_node) = (*fast).next.as_mut() { fast = next_node; slow = match (*slow).next.as_mut() { Some(node) => node, None => break, }; }

Move both pointers forward until fast reaches end

let node_to_remove = (*slow).next.take(); if let Some(mut node) = node_to_remove { (*slow).next = node.next.take(); }

Remove the target node by skipping it in the list

Output

Original list:

1 -> 2 -> 3 -> 4 -> 5 -> null

List after removing 2th node from end:

1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we only use a few pointers, no extra data structures

vs Alternative: Compared to two-pass approach (count length then remove), this one-pass method is more efficient and cleaner

Edge Cases

Removing the first node (n equals list length)

Dummy node helps remove head safely without special cases

DSA Rust

let mut dummy = Box::new(ListNode { val: 0, next: head });

List with only one node and n=1

Returns empty list (null) after removal

DSA Rust

if let Some(node) = node_to_remove { (*slow).next = node.next.take(); }

n is larger than list length

Function returns original list without changes

DSA Rust

None => return dummy.next,

When to Use This Pattern

When asked to remove or find the nth node from the end in a linked list, use two pointers spaced n apart to find the target in one pass.

Common Mistakes

Mistake: Not using a dummy node and failing when removing the head node
Fix: Always use a dummy node before head to simplify edge cases

Mistake: Moving slow pointer too early or too late, causing wrong node removal
Fix: Move fast pointer n steps first, then move both pointers together until fast reaches end

Summary

Removes the nth node from the end of a singly linked list in one pass.

Use when you need efficient removal from the end without counting list length first.

The key is to keep two pointers n nodes apart so slow lands just before the target 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