*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #19 (*Medium*): Remove Nth Node From End of List

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given the

`head`

of a linked list, remove the`n`

th node from the end of the list and return its`head`

.

Follow up: Could you do this in one pass?

####
*Examples:*

*Examples:*

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

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

Example 3: Input: head = [1,2], n = 1 Output: [1]

####
*Constraints:*

*Constraints:*

- The number of nodes in the list is
`sz`

.`1 <= sz <= 30`

`0 <= Node.val <= 100`

`1 <= n <= sz`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

With a singly linked list, the *only* way to find the end of the list, and thus the **n**'th node from the end, is to actually iterate all the way to the end. The challenge here is attemping to find the solution in only one pass. A naive approach here might be to store pointers to each node in an array, allowing us to calculate the **n**'th from the end once we reach the end, but that would take **O(M) extra space**, where **M** is the length of the linked list.

A slightly less naive approach would be to only store only the last **n+1** node pointers in the array. This could be achieved by overwriting the elements of the storage array in circlular fashion as we iterate through the list. This would lower the **space complexity** to **O(N+1)**.

In order to solve this problem in only one pass and **O(1) extra space**, however, we would need to find a way to *both* reach the end of the list with one pointer *and also* reach the **n**'th node from the end simultaneously with a second pointer.

To do that, we can simply stagger our two pointers by **n** nodes by giving the first pointer (**fast**) a head start before starting the second pointer (**slow**). Doing this will cause **slow** to reach the **n**'th node from the end at the same time that **fast** reaches the end.

Since we will need access to the node *before* the target node in order to remove the target node, we can use **fast.next == null** as our exit condition, rather than **fast == null**, so that we stop one node earlier.

This will unfortunately cause a problem when **n** is the same as the length of the list, which would make the first node the target node, and thus make it impossible to find the node *before* the target node. If that's the case, however, we can just **return head.next** without needing to stitch together the two sides of the target node.

Otherwise, once we succesfully find the node *before* the target, we can then stitch it together with the node *after* the target, and then **return head**.

####
*Implementation:*

*Implementation:*

There are only minor differences between the code of all four languages.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var removeNthFromEnd = function(head, n) {
let fast = head, slow = head
for (let i = 0; i < n; i++) fast = fast.next
if (!fast) return head.next
while (fast.next) fast = fast.next, slow = slow.next
slow.next = slow.next.next
return head
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
fast, slow = head, head
for _ in range(n): fast = fast.next
if not fast: return head.next
while fast.next: fast, slow = fast.next, slow.next
slow.next = slow.next.next
return head
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head, slow = head;
for (int i = 0; i < n; i++) fast = fast.next;
if (fast == null) return head.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *fast = head, *slow = head;
for (int i = 0; i < n; i++) fast = fast->next;
if (!fast) return head->next;
while (fast->next) fast = fast->next, slow = slow->next;
slow->next = slow->next->next;
return head;
}
};
```

## Discussion (1)

My Java Solution :

github.com/Rohithv07/LeetCodeTopIn...