19. Remove Nth Node From End of List - Explanation

Description

Given the head of a linked list and an integer n, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4], n = 2

Output: [1,2,4]

Example 2:

Input: head = [5], n = 1

Output: []

Example 3:

Input: head = [1,2], n = 2

Output: [2]

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Topics

Linked List Two Pointers

Recommended Time & Space Complexity

You should aim for a solution with O(N) time and O(1) space, where N is the length of the given list.

Hint 1

A brute force solution would involve storing the nodes of the list into an array, removing the nth node from the array, and then converting the array back into a linked list to return the new head. However, this requires O(N) extra space. Can you think of a better approach to avoid using extra space? Maybe you should first solve with a two pass approach.

Hint 2

We can use a two-pass approach by first finding the length of the list, N. Since removing the nth node from the end is equivalent to removing the (N - n)th node from the front, as they both mean the same. How can you remove the node in a linked list?

Hint 3

For example, consider a three-node list [1, 2, 3]. If we want to remove 2, we update the next pointer of 1 (initially pointing to 2) to point to the node after 2, which is 3. After this operation, the list becomes [1, 3], and we return the head. But, can we think of a more better approach? Maybe a greedy calculation can help.

Hint 4

We can avoid a separate length-counting pass with two pointers. Move the first pointer n steps ahead from the head. Then, start another pointer second at a dummy node before the head and iterate both pointers simultaneously until first reaches null. At this point, the second pointer is just before the node to be removed. We then remove the node that is next to the second pointer. Why does this work?

Hint 5

This works because first stays n nodes ahead of second.next. When first reaches the end, second.next is exactly the nth node from the end. This positioning allows us to remove that node efficiently.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Linked List Fundamentals - Understanding how singly linked lists work, including node structure and traversal
Two Pointers Technique - Using multiple pointers to track different positions in a data structure simultaneously
Dummy Node Pattern - Creating a sentinel node to simplify edge cases like removing the head node

1. Brute Force

Intuition

We store all nodes in an array so we can directly access the node that is n positions from the end.
Once we know which node to delete, we simply adjust the next pointer of the previous node.

Algorithm

Traverse the linked list and push every node into an array.
Compute the index of the node to remove: len(nodes) - n.
If this index is 0, it means the head must be removed → return head.next.
Otherwise, connect nodes[removeIndex - 1].next to nodes[removeIndex].next.
Return the updated head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next

        removeIndex = len(nodes) - n
        if removeIndex == 0:
            return head.next

        nodes[removeIndex - 1].next = nodes[removeIndex].next
        return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     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) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            nodes.add(cur);
            cur = cur.next;
        }

        int removeIndex = nodes.size() - n;
        if (removeIndex == 0) {
            return head.next;
        }

        nodes.get(removeIndex - 1).next = nodes.get(removeIndex).next;
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> nodes;
        ListNode* cur = head;
        while (cur != nullptr) {
            nodes.push_back(cur);
            cur = cur->next;
        }

        int removeIndex = nodes.size() - n;
        if (removeIndex == 0) {
            return head->next;
        }

        nodes[removeIndex - 1]->next = nodes[removeIndex]->next;
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number} n
     * @return {ListNode}
     */
    removeNthFromEnd(head, n) {
        const nodes = [];
        let cur = head;
        while (cur) {
            nodes.push(cur);
            cur = cur.next;
        }

        const removeIndex = nodes.length - n;
        if (removeIndex === 0) {
            return head.next;
        }

        nodes[removeIndex - 1].next = nodes[removeIndex].next;
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        var nodes = new List<ListNode>();
        var cur = head;
        while (cur != null) {
            nodes.Add(cur);
            cur = cur.next;
        }

        int removeIndex = nodes.Count - n;
        if (removeIndex == 0) {
            return head.next;
        }

        nodes[removeIndex - 1].next = nodes[removeIndex].next;
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    nodes := []*ListNode{}
    cur := head
    for cur != nil {
        nodes = append(nodes, cur)
        cur = cur.Next
    }

    removeIndex := len(nodes) - n
    if removeIndex == 0 {
        return head.Next
    }

    nodes[removeIndex-1].Next = nodes[removeIndex].Next
    return head
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val nodes = mutableListOf<ListNode?>()
        var cur = head

        while (cur != null) {
            nodes.add(cur)
            cur = cur.next
        }

        val removeIndex = nodes.size - n
        if (removeIndex == 0) {
            return head?.next
        }

        nodes[removeIndex - 1]?.next = nodes[removeIndex]?.next
        return head
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var nodes: [ListNode] = []
        var cur = head

        while cur != nil {
            nodes.append(cur!)
            cur = cur?.next
        }

        let removeIndex = nodes.count - n
        if removeIndex == 0 {
            return head?.next
        }

        nodes[removeIndex - 1].next = nodes[removeIndex].next
        return head
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut nodes: Vec<i32> = Vec::new();
        let mut cur = &head;
        while let Some(node) = cur {
            nodes.push(node.val);
            cur = &node.next;
        }

        let remove_index = nodes.len() - n as usize;
        let mut dummy = Box::new(ListNode { val: 0, next: head });
        let mut cur = &mut dummy;
        for _ in 0..remove_index {
            cur = cur.next.as_mut().unwrap();
        }
        let next = cur.next.as_mut().unwrap().next.take();
        cur.next = next;
        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$

2. Iteration (Two Pass)

Intuition

We first count how many nodes are in the list.
Once we know the total length, the node to delete is at position N - n from the start.
We run a second pass to reach the node just before it and skip it.

Algorithm

Traverse the list once to compute total nodes N.
Compute removeIndex = N - n.
If removeIndex == 0, delete the head → return head.next.
Traverse again until reaching the node before removeIndex.
Update its next pointer to skip the unwanted node.
Return the modified head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        N = 0
        cur = head
        while cur:
            N += 1
            cur = cur.next

        removeIndex = N - n
        if removeIndex == 0:
            return head.next

        cur = head
        for i in range(N - 1):
            if (i + 1) == removeIndex:
                cur.next = cur.next.next
                break
            cur = cur.next
        return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     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) {
        int N = 0;
        ListNode cur = head;
        while (cur != null) {
            N++;
            cur = cur.next;
        }

        int removeIndex = N - n;
        if (removeIndex == 0) {
            return head.next;
        }

        cur = head;
        for (int i = 0; i < N - 1; i++) {
            if ((i + 1) == removeIndex) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int N = 0;
        ListNode* cur = head;
        while (cur != nullptr) {
            N++;
            cur = cur->next;
        }

        int removeIndex = N - n;
        if (removeIndex == 0) {
            return head->next;
        }

        cur = head;
        for (int i = 0; i < N - 1; i++) {
            if ((i + 1) == removeIndex) {
                cur->next = cur->next->next;
                break;
            }
            cur = cur->next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number} n
     * @return {ListNode}
     */
    removeNthFromEnd(head, n) {
        let N = 0;
        let cur = head;
        while (cur) {
            N++;
            cur = cur.next;
        }

        const removeIndex = N - n;
        if (removeIndex === 0) {
            return head.next;
        }

        cur = head;
        for (let i = 0; i < N - 1; i++) {
            if (i + 1 === removeIndex) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        int N = 0;
        ListNode cur = head;
        while (cur != null) {
            N++;
            cur = cur.next;
        }

        int removeIndex = N - n;
        if (removeIndex == 0) {
            return head.next;
        }

        cur = head;
        for (int i = 0; i < N - 1; i++) {
            if (i + 1 == removeIndex) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    N := 0
    cur := head
    for cur != nil {
        N++
        cur = cur.Next
    }

    removeIndex := N - n
    if removeIndex == 0 {
        return head.Next
    }

    cur = head
    for i := 0; i < N-1; i++ {
        if (i + 1) == removeIndex {
            cur.Next = cur.Next.Next
            break
        }
        cur = cur.Next
    }
    return head
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        var N = 0
        var cur = head

        while (cur != null) {
            N++
            cur = cur.next
        }

        val removeIndex = N - n
        if (removeIndex == 0) {
            return head?.next
        }

        cur = head
        for (i in 0 until N - 1) {
            if (i + 1 == removeIndex) {
                cur?.next = cur?.next?.next
                break
            }
            cur = cur?.next
        }
        return head
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var N = 0
        var cur = head
        while cur != nil {
            N += 1
            cur = cur?.next
        }

        let removeIndex = N - n
        if removeIndex == 0 {
            return head?.next
        }

        cur = head
        for i in 0..<(N - 1) {
            if (i + 1) == removeIndex {
                cur?.next = cur?.next?.next
                break
            }
            cur = cur?.next
        }
        return head
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut count = 0;
        let mut cur = &head;
        while let Some(node) = cur {
            count += 1;
            cur = &node.next;
        }

        let remove_index = count - n as usize;
        if remove_index == 0 {
            return head.unwrap().next;
        }

        let mut dummy = Box::new(ListNode { val: 0, next: head });
        let mut cur = &mut dummy;
        for _ in 0..remove_index {
            cur = cur.next.as_mut().unwrap();
        }
        let next = cur.next.as_mut().unwrap().next.take();
        cur.next = next;
        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$

3. Recursion

Intuition

Recursion naturally processes the list from the end toward the start.
When the recursive calls unwind, we count backwards.
When the count reaches the nth node from the end, we skip it by returning head.next instead of the current node.

Algorithm

Recursively go to the end of the list.
As recursion unwinds, decrement n each time you return.
When n becomes 0, this is the node to delete → return its next node.
Otherwise, return the current node to rebuild the list.
The head of the resulting rebuilt list is the final answer.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def rec(self, head, n):
        if not head:
            return None

        head.next = self.rec(head.next, n)
        n[0] -= 1
        if n[0] == 0:
            return head.next
        return head

    def removeNthFromEnd(self, head, n):
        return self.rec(head, [n])

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

public class Solution {
    public ListNode rec(ListNode head, int[] n) {
        if (head == null) {
            return null;
        }

        head.next = rec(head.next, n);
        n[0]--;
        if (n[0] == 0) {
            return head.next;
        }
        return head;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        return rec(head, new int[]{n});
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* rec(ListNode* head, int& n) {
        if (!head) {
            return NULL;
        }

        head -> next = rec(head -> next, n);
        n--;
        if (n == 0) {
            return head -> next;
        }
        return head;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        return rec(head, n);
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number[]} n
     * @return {ListNode}
     */
    rec(head, n) {
        if (!head) {
            return null;
        }

        head.next = this.rec(head.next, n);
        n[0]--;
        if (n[0] === 0) {
            return head.next;
        }
        return head;
    }

    /**
     * @param {ListNode} head
     * @param {number} n
     * @return {ListNode}
     */
    removeNthFromEnd(head, n) {
        return this.rec(head, [n]);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode rec(ListNode head, ref int n) {
        if (head == null) {
            return null;
        }

        head.next = rec(head.next, ref n);
        n--;
        if (n == 0) {
            return head.next;
        }
        return head;
    }

    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        return rec(head, ref n);
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rec(head *ListNode, n *int) *ListNode {
    if head == nil {
        return nil
    }

    head.Next = rec(head.Next, n)
    (*n)--

    if *n == 0 {
        return head.Next
    }
    return head
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    return rec(head, &n)
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    private fun rec(head: ListNode?, n: IntArray): ListNode? {
        if (head == null) {
            return null
        }

        head.next = rec(head.next, n)
        n[0]--

        return if (n[0] == 0) {
            head.next
        } else {
            head
        }
    }

    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        return rec(head, intArrayOf(n))
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func rec(_ head: ListNode?, _ n: inout Int) -> ListNode? {
        if head == nil {
            return nil
        }

        head?.next = rec(head?.next, &n)
        n -= 1
        if n == 0 {
            return head?.next
        }
        return head
    }

    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var n = n
        return rec(head, &n)
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        fn rec(head: Option<Box<ListNode>>, n: &mut i32) -> Option<Box<ListNode>> {
            if let Some(mut node) = head {
                node.next = rec(node.next, n);
                *n -= 1;
                if *n == 0 {
                    return node.next;
                }
                Some(node)
            } else {
                None
            }
        }
        let mut n = n;
        rec(head, &mut n)
    }
}

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$ for recursion stack.

4. Two Pointers

Intuition

Use two pointers so that the gap between them is exactly n.
Move the right pointer n steps ahead first.
Then move both pointers together.
When the right pointer reaches the end, the left pointer will be just before the node we must remove.
This avoids a separate length-counting pass, while still traversing the list in O(N) time.
The key benefit is that the n-node gap tells us where to delete without storing nodes or computing the length first.

Algorithm

Create a dummy node pointing to the head (helps handle deletion of the first node).
Set two pointers:
- left at dummy
- right at head
Move right forward n steps.
Move both pointers until right reaches the end.
Now left.next is the node to delete → skip it by doing left.next = left.next.next.
Return dummy.next as the updated head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

        while right:
            left = left.next
            right = right.next

        left.next = left.next.next
        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = head;

        while (n > 0) {
            right = right.next;
            n--;
        }

        while (right != null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* left = dummy;
        ListNode* right = head;

        while (n > 0) {
            right = right->next;
            n--;
        }

        while (right != nullptr) {
            left = left->next;
            right = right->next;
        }

        left->next = left->next->next;
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    /**
     * @param {ListNode} head
     * @param {number} n
     * @return {ListNode}
     */
    removeNthFromEnd(head, n) {
        const dummy = new ListNode(0, head);
        let left = dummy;
        let right = head;

        while (n > 0) {
            right = right.next;
            n--;
        }

        while (right !== null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = head;

        while (n > 0) {
            right = right.next;
            n--;
        }

        while (right != null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    left := dummy
    right := head

    for n > 0 {
        right = right.Next
        n--
    }

    for right != nil {
        left = left.Next
        right = right.Next
    }

    left.Next = left.Next.Next
    return dummy.Next
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummy = ListNode(0).apply { next = head }
        var left: ListNode? = dummy
        var right: ListNode? = head

        var count = n
        while (count > 0) {
            right = right?.next
            count--
        }

        while (right != null) {
            left = left?.next
            right = right.next
        }

        left?.next = left?.next?.next
        return dummy.next
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0, head)
        var left: ListNode? = dummy
        var right: ListNode? = head
        var n = n

        while n > 0 {
            right = right?.next
            n -= 1
        }

        while right != nil {
            left = left?.next
            right = right?.next
        }

        left?.next = left?.next?.next
        return dummy.next
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub 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 len = 0;
        {
            let mut cur = &dummy.next;
            while let Some(node) = cur {
                len += 1;
                cur = &node.next;
            }
        }
        let target = len - n as usize;
        let mut cur = &mut dummy;
        for _ in 0..target {
            cur = cur.next.as_mut().unwrap();
        }
        let next = cur.next.as_mut().unwrap().next.take();
        cur.next = next;
        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Handle Head Removal

When n equals the length of the list, the head node itself must be removed. Without a dummy node or explicit check for this case, the code may crash or return incorrect results. Always verify your solution works when the target is the first node.

Off-by-One Errors in Pointer Positioning

The two-pointer technique requires the left pointer to stop at the node before the one to delete. A common mistake is advancing right by n-1 instead of n steps, causing the wrong node to be removed. Carefully trace through a small example to confirm your gap is correct.

Not Returning the Updated Head

After modifying the list, forgetting to return dummy.next (or the updated head) results in returning a stale reference. This is especially problematic when the original head was deleted. Always ensure your return statement reflects any structural changes to the list.