> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/linked-list/0019.-remove-nth-node-from-end-of-list.md).

# 0019. Remove Nth Node From End of List

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0019-remove-nth-node-from-end-of-list)

Given the `head` of a linked list, **remove the `nth` node from the end of the list and return its head.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Use a hash table to record each node's location needs O(n). Instead, we could **manipulate two pointers to create a gap between two pointers to find the target node**, and that **only required O(1) space complexity.**
{% endhint %}

1. Move the fast-pointer **forward to create `n` gaps apart from the slow-pointer**
2. If the fast-point now points to null, it means the first node is the one to be removed
3. Move forward the fast-pointer and slow-pointer together **until the next node of the fast-pointer is null**
4. Now, **the next node of the slow-pointer is the one that needs to be removed.** So then break the link by **`slowP.next = slowP.next.next`** and return the head
   {% endtab %}
   {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # (base case)
        if not head.next and n == 1: return None
        
        # ==================================================
        #  Linked List + Two Pointer                       =
        # ==================================================
        # time  : O(n), one pass
        # space : O(1)
        
        slowP, fastP = head, head
        
        # move fast-pointer to keep the gap(n) apart from slow-pointer
        for i in range(n): fastP = fastP.next
        
        # n == length of the linked list
        if not fastP: return head.next
        
        # move fast-pointer to the end, maintaining the gap
        while fastP.next: slowP, fastP = slowP.next, fastP.next
            
        slowP.next = slowP.next.next
        return head
        
        '''
        # ==================================================
        #  Linked List + Hash Table                        =
        # ==================================================
        # time  : O(n), one pass
        # space : O(n)
        
        ret = head
        
        index = 0
        table = dict()
        while head:
            table[index] = head
            head = head.next
            index += 1
        
        if n == index: return ret.next
        
        # find the node before the one that needs to be removed
        node = table[index - n - 1]
        node.next = node.next.next
        
        return ret
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(1)
     */
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /* base case */
        if(head.next == null && n == 1) return null;
        
        ListNode slowP = head, fastP = head;
        
        /* Move fast-pointer so that the gap between two pointers is n nodes apart */
        for (int i=0 ; i<n ; i++) fastP = fastP.next;
        
        /* nth node from the end points to HEAD */
        if(fastP == null) return head.next;
            
        /* Move fast-pointer to the end, maintaining the gap */
        while (fastP.next != null) {
            slowP = slowP.next;
            fastP = fastP.next;
        }
        
        slowP.next = slowP.next.next;
        return head;
    }
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://yyloumike.gitbook.io/leetcode/linked-list/0019.-remove-nth-node-from-end-of-list.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.