---
description: '# Medium'
---

# 19. Remove Nth Node From End of List

{% hint style="info" %}
Key idea: Two methods.

1. Two pass method: get the legnth of the **linklist**, then remove `(l-n)th` from beginning. Time = $$O(l+l-n)=O(l).$$&#x20;
2. One pass method: two pointers, the **first ptr** is n ahead of the **second ptr**, once **first ptr** reach the end, remove **second ptr->next**. Time = $$O(l)$$ .
{% endhint %}

{% tabs %}
{% tab title="C++(method 1)" %}
```cpp
/**
 * 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* node = head;
        int l = 0;
        while(node) {
            node = node->next;
            l ++;
        }
        
        // edge case
        if(l == n) {
            head = head->next;
            return head;
        }
        node = head;
        for(int i = 0; i < l-n-1; i ++) {
            node = node->next;
        }
        node->next = node->next->next;
        return head;
    }
};
```
{% endtab %}

{% tab title="C++(method 2)" %}
```cpp
/**
 * 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 *dump = new ListNode(-1), *first, *second;
        dump->next = head;
        first = dump;
        second = dump;
        while(n) {
            first = first->next;
            n --;
        }
        
        while(first->next) {
            first = first->next;
            second = second->next;
        }
        
        second->next = second->next->next;
        return dump->next;
    }
};
```
{% endtab %}
{% endtabs %}

{% hint style="danger" %}
In method 2, must set **dump node** to avoid the mistake when deleting the **head node**.

In these two methods, pay attention to the case of deleting the **head node**.
{% endhint %}
