# Remove Nth Node From End of List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-nth-node-from-end-of-list)
Canonical: https://scaleengineer.com/dsa/problems/remove-nth-node-from-end-of-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Citrix](https://scaleengineer.com/companies/citrix)
---
## Problem
Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head.

**Example 1:**

![](https://assets.glich.co/dsa/remove-nth-node-from-end-of-list/image0.jpg) 

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

**Follow up:** Could you do this in one pass?

# Approaches
## Two-Pass Algorithm
This approach involves two separate traversals of the linked list. The first pass is to determine the total length of the list, and the second pass is to locate and remove the desired node.
**Time:** O(L) · **Space:** O(1)
**Pros:** Simple to understand and implement.; The logic is straightforward and follows a clear two-step process.
**Cons:** Inefficient compared to a single-pass solution as it requires traversing the list twice.
### Explanation
The core idea is to first find the length of the list, let's say `L`. The nth node from the end is equivalent to the `(L - n + 1)`-th node from the beginning. To remove this node, we need to find its predecessor, which is the `(L - n)`-th node from the beginning.

To handle the edge case where the head of the list needs to be removed (i.e., when `n` is equal to the list's length), we use a `dummy` node. This `dummy` node points to the original `head`, simplifying the removal logic.

After calculating the length `L` in the first pass, we start a second traversal from the `dummy` node. We iterate `L - n` times to reach the node just before the one we want to delete. Finally, we update the `next` pointer of this predecessor node to skip the target node, effectively removing it from the list.

```java
/**
 * 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);
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }

        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}
```
### Algorithm
1.  Create a `dummy` node and set its `next` pointer to the `head` of the list. This simplifies handling the edge case of removing the head node.
2.  Traverse the list from the `head` to the end to calculate its total length, let's call it `L`.
3.  Calculate the position of the node to be removed from the beginning. The nth node from the end is the `(L - n)`-th node from the start (0-indexed). We need to find the node *before* it.
4.  Initialize a pointer, `current`, to the `dummy` node.
5.  Traverse `L - n` steps from the `dummy` node. The `current` pointer will now be at the node just before the one we want to remove.
6.  Update the `next` pointer of the `current` node to skip the target node: `current.next = current.next.next`.
7.  Return `dummy.next`, which is the new head of the modified list.

## One-Pass Algorithm with Two Pointers
This is a more optimized approach that solves the problem in a single pass. It uses two pointers, often called `fast` and `slow`, to find the nth node from the end without first needing to calculate the list's length.
**Time:** O(L) · **Space:** O(1)
**Pros:** Highly efficient as it solves the problem in a single pass over the list.; Constant space complexity.; An elegant and common pattern for solving linked list problems involving relative positions.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the two-pass method.
### Explanation
The strategy is to maintain a fixed-size gap of `n` nodes between a `fast` and a `slow` pointer. We start by creating a `dummy` node pointing to the `head` to simplify edge cases. Both `fast` and `slow` pointers are initialized to this `dummy` node.

First, we advance the `fast` pointer `n + 1` steps into the list. This creates the necessary gap. After establishing the gap, we move both `fast` and `slow` pointers forward one step at a time. We continue this until the `fast` pointer reaches the end of the list (`null`).

Because of the initial gap, when `fast` reaches the end, the `slow` pointer will be positioned exactly at the node *before* the nth node from the end. We can then easily remove the target node by updating `slow.next` to point to `slow.next.next`. This method cleverly uses the relative distance between two pointers to find the target node in a single traversal.

```java
/**
 * 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 slow = dummy;
        ListNode fast = dummy;

        // Move fast pointer n + 1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove the nth node from the end
        slow.next = slow.next.next;

        return dummy.next;
    }
}
```
### Algorithm
1.  Create a `dummy` node that points to the `head` of the list. This helps in handling edge cases like removing the first node.
2.  Initialize two pointers, `slow` and `fast`, both pointing to the `dummy` node.
3.  Move the `fast` pointer `n + 1` steps ahead of the `slow` pointer. This creates a fixed gap of `n` nodes between them.
4.  Now, move both `slow` and `fast` pointers one step at a time, maintaining the gap, until the `fast` pointer reaches the end of the list (`null`).
5.  When `fast` is `null`, the `slow` pointer will be positioned at the node just before the nth node from the end.
6.  Update `slow.next` to `slow.next.next` to bypass and remove the target node.
7.  Return `dummy.next`, which is the head of the modified list.

# Solutions
### CSharp

```csharp
/** * 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 fast = dummy , slow = dummy ; while ( n -- > 0 ) { fast = fast . next ; } while ( fast . next != null ) { slow = slow . next ; fast = fast . next ; } slow . next = slow . next . next ; return dummy . next ; } }
```

### Java

```java
/** * 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 fast = dummy , slow = dummy ; while ( n -- > 0 ) { fast = fast . next ; } while ( fast . next != null ) { slow = slow . next ; fast = fast . next ; } slow . next = slow . next . next ; return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function ( head , n ) { const dummy = new ListNode ( 0 , head ); let fast = dummy , slow = dummy ; while ( n -- ) { fast = fast . next ; } while ( fast . next ) { slow = slow . next ; fast = fast . next ; } slow . next = slow . next . next ; return dummy . next ; };
```

### CPP

```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 * dummy = new ListNode ( 0 , head ); ListNode * fast = dummy ; ListNode * slow = dummy ; while ( n -- ) { fast = fast -> next ; } while ( fast -> next ) { slow = slow -> next ; fast = fast -> next ; } slow -> next = slow -> next -> next ; return dummy -> next ; } };
```

### Python

```python
# 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 ( next = head ) fast = slow = dummy for _ in range ( n ): fast = fast . next while fast . next : slow , fast = slow . next , fast . next slow . next = slow . next . next return dummy . next
```