DSA Series Day 21 Remove Nth Node From End of List in Java, Python and Rust

DSA Series Day 21: Remove Nth Node From End of List in Java, Python and Rust

Remove Nth Node From End of List is Day 21 of the Tekraze DSA series, and it is the cleanest place to learn the dummy node and the fixed gap two pointer trick. We are still in the linked list chapter, right after Day 20, Linked List Cycle. The problem looks small, but the two habits it teaches show up in interview after interview.

Also Read: Linked List Cycle: 6 Best Tips to Solve It Easily for the slow and fast pointer idea this post builds on.

What is the Remove Nth Node From End of List problem?

Given the head of a singly linked list and a number n, remove the nth node counted from the end and return the head of the changed list. You can assume n is always valid, so it sits between 1 and the length of the list. It is the same task as the LeetCode problem of the same name.

text

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5
Input:  head = 1, n = 1
Output: empty list
Input:  head = 1 -> 2, n = 1
Output: 1

How should you think about it in plain words?

A singly linked list only lets you walk forward, so you can’t count backwards from the tail. The trick is to turn “n from the end” into a distance. Send one pointer n steps ahead, then move both pointers together.

When the front pointer reaches the last node, the back pointer sits right before the node you want to delete. Think of two friends holding a rope of fixed length while walking down a road.

Two pointers holding a fixed gap, the idea behind Remove Nth Node From End of List
DSA Series Day 21: Remove Nth Node From End of List in Java, Python and Rust 7

What does the brute force approach look like for Remove Nth Node From End of List?

Walk the list once to count its length L. The node to remove is at position L – n from the start, so walk again to the node just before it and skip over the target.

python

def remove_nth_brute(head, n):
    length, cur = 0, head
    while cur:
        length += 1
        cur = cur.next
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(length - n):
        prev = prev.next
    prev.next = prev.next.next
    return dummy.next

This is O(n) time and O(1) space, which is honestly fine. It just takes two passes, and the classic follow up asks you to solve Remove Nth Node From End of List in a single pass.

How do we get the optimal Remove Nth Node From End of List solution?

Put a dummy node in front of the head so that removing the very first node is no different from removing any other. Start fast and slow at the dummy. Move fast forward n times. Then move both one step at a time until fast.next is null.

Now slow.next is the node to drop, so set slow.next = slow.next.next and return dummy.next. If you have read Day 19, Merge Two Sorted Lists, you already know why the dummy node saves you from special cases.

Time is O(n) because each pointer visits every node at most once. Space is O(1) since we only keep a dummy node and two pointers. If you want a refresher on why these bounds hold, read our Big O helper post on time and space complexity.

Dummy node placed before the head to simplify Remove Nth Node From End of List
DSA Series Day 21: Remove Nth Node From End of List in Java, Python and Rust 8

Which approach should you pick?

Here is how the three common ways to solve Remove Nth Node From End of List compare.

ApproachPassesTimeExtra space
Count length, then walk2O(n)O(1)
Push nodes on a stack, pop n2O(n)O(n)
Fast and slow with a gap1O(n)O(1)

Java solution for Remove Nth Node From End of List

java

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
    static ListNode build(int[] vals) {
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; }
        return dummy.next;
    }
    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (; head != null; head = head.next) out.add(head.val);
        return out;
    }
    public static void main(String[] args) {
        int[][] in = {{1, 2, 3, 4, 5}, {1}, {1, 2}, {1, 2}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}};
        int[] ns = {2, 1, 1, 2, 5, 1};
        String[] want = {"[1, 2, 3, 5]", "[]", "[1]", "[2]", "[2, 3, 4, 5]", "[1, 2, 3, 4]"};
        Solution s = new Solution();
        for (int i = 0; i < in.length; i++) {
            String got = toList(s.removeNthFromEnd(build(in[i]), ns[i])).toString();
            if (!got.equals(want[i])) throw new AssertionError("case " + i + ": " + got);
            System.out.println(Arrays.toString(in[i]) + " " + ns[i] + " -> " + got);
        }
        System.out.println("All Java tests passed");
    }
}

Python solution for Remove Nth Node From End of List

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next
def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next
def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out
if __name__ == "__main__":
    tests = [
        ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
        ([1], 1, []),
        ([1, 2], 1, [1]),
        ([1, 2], 2, [2]),
        ([1, 2, 3, 4, 5], 5, [2, 3, 4, 5]),
        ([1, 2, 3, 4, 5], 1, [1, 2, 3, 4]),
    ]
    for vals, n, want in tests:
        got = to_list(remove_nth_from_end(build(vals), n))
        assert got == want, (vals, n, got, want)
        print(vals, n, "->", got)
    print("All Python tests passed")

Rust solution for Remove Nth Node From End of List

Rust’s borrow checker won’t let two pointers hold the same Box list at once while one of them changes it. So the idiomatic Rust answer to Remove Nth Node From End of List counts the length first, then walks a single mutable reference from the dummy node to the spot and unlinks the target. It is still O(n) time and O(1) space. The Rust Book chapter on ownership explains why, and Option::take is the method that lets us unlink the node safely.

rust

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
    // Count the nodes first, because Rust will not let two pointers share the list.
    let mut len = 0;
    let mut cur = head.as_ref();
    while let Some(node) = cur {
        len += 1;
        cur = node.next.as_ref();
    }
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut prev = &mut dummy;
    for _ in 0..(len - n) {
        prev = prev.next.as_mut().unwrap();
    }
    let removed = prev.next.take();
    prev.next = removed.and_then(|node| node.next);
    dummy.next
}
fn build(vals: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &v in vals.iter().rev() {
        head = Some(Box::new(ListNode { val: v, next: head }));
    }
    head
}
fn to_vec(mut head: &Option<Box<ListNode>>) -> Vec<i32> {
    let mut out = vec![];
    while let Some(node) = head {
        out.push(node.val);
        head = &node.next;
    }
    out
}
fn main() {
    let tests: Vec<(Vec<i32>, i32, Vec<i32>)> = vec![
        (vec![1, 2, 3, 4, 5], 2, vec![1, 2, 3, 5]),
        (vec![1], 1, vec![]),
        (vec![1, 2], 1, vec![1]),
        (vec![1, 2], 2, vec![2]),
        (vec![1, 2, 3, 4, 5], 5, vec![2, 3, 4, 5]),
        (vec![1, 2, 3, 4, 5], 1, vec![1, 2, 3, 4]),
    ];
    for (vals, n, want) in tests {
        let got = to_vec(&remove_nth_from_end(build(&vals), n));
        assert_eq!(got, want);
        println!("{:?} {} -> {:?}", vals, n, got);
    }
    println!("All Rust tests passed");
}

All three programs ran the classic 1 to 5 example with n = 2, a single node list, a two node list with n = 1 and n = 2, removing the head of a five node list, and removing its tail. Every check passed in Java, Python and Rust.

What are the 6 tips and tricks for an easy Remove Nth Node From End of List solution?

  1. Spot the pattern. Any question that says kth from the end, or middle of the list, is begging for two pointers with a gap or with different speeds.
  2. Always use a dummy node. When the head itself might be removed, a dummy in front saves you a messy special case.
  3. Count the gap carefully. Start both pointers on the dummy and move fast exactly n steps, then loop while fast.next exists. That leaves slow just before the target.
  4. Test the edges first. Try a one node list, n equal to the length, and n = 1 before you trust your loop.
  5. Draw it before you code. Sketch five boxes, mark fast and slow, and step through the loop by hand once.
  6. Explain both passes in interviews. Mention the two pass counting idea in a sentence, then say you can do it in one pass with a fixed gap.

What are the common mistakes in Remove Nth Node From End of List?

  • Forgetting the dummy node and crashing when n equals the length of the list.
  • Moving fast n + 1 or n – 1 times and deleting the wrong neighbour.
  • Looping while fast is not null instead of fast.next, which leaves slow one step too far.
  • Returning head instead of dummy.next after the old head was removed.
  • Trying to walk backwards, which a singly linked list can’t do.
 Linked list after Remove Nth Node From End of List with the second last node skipped
DSA Series Day 21: Remove Nth Node From End of List in Java, Python and Rust 9

Where is the Remove Nth Node From End of List pattern used in the real world?

The fixed gap idea appears whenever you need the last few items of a stream you can only read forward. Log tools that show the last N lines, undo histories with a size limit, and network buffers that keep a sliding tail of packets all lean on it.

The dummy head trick is everywhere in real list and queue code, including allocators and schedulers, because it removes special cases at the front.

Frequently asked questions

What is the Remove Nth Node From End of List problem?

You get the head of a singly linked list and a number n, and you remove the nth node counted from the end, then return the head of the updated list.

How do you solve Remove Nth Node From End of List in one pass?

Put a dummy node before the head, move a fast pointer n steps ahead, then move fast and slow together until fast reaches the last node. Slow is now just before the target, so skip over it.

Why use a dummy node in Remove Nth Node From End of List?

If n equals the length of the list you have to remove the head. A dummy node in front means the head is handled exactly like any other node, so there is no special case.

What is the time and space complexity of Remove Nth Node From End of List?

Both the two pass and the one pass solutions run in O(n) time and O(1) extra space. The one pass version just touches the list once.

Can you solve Remove Nth Node From End of List without two pointers?

Yes. Count the length first and then walk to position length minus n, or push all nodes on a stack and pop n of them. Both work, but they need two passes or extra memory.

Conclusion

Remove Nth Node From End of List comes down to one picture: a dummy node, and two pointers holding a fixed gap. Start with the edge cases, then write the one pass loop from memory. Day 22 continues the DSA series, so keep following along.

Content Protection by DMCA.com
Spread the love
Scroll to Top
×