*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;
}
};
```

## Top comments (8)

Can you explain how

headholds the new list after deletion.slowholds remaining values of head after n from beginning and after we delete the nth value fromslowusingslow.next=slow.next.next;, how does head hold exact list after deletion?I'm not sure I understand the question. The

headpointer is never overwritten, so it always represents the start of the entire linked list. That doesn't change when the node deletion occurs.The function returns

headat the end which has the list after the deleting the required node. How does this happen when we aren't updating head ?The variable

headjust contains a pointer to the start of the linked list. It doesn't contain the entire linked list. So any changes made to the nodes of the list and their connections will affect a traversal of the list starting athead.Got it. Thanks for your reply ðŸ˜ƒ

can you explain this line

`if (!fast) return head.next`

?Sure. The

bang operator(`!`

) returns the oppositeboolean valueof the thing to which it's attached. In this case,`fast`

is either anode reference, which evaluates astruthy, or it's`null`

, which isfalsy.So

`!fast`

returns`true`

if`fast`

is`null`

, but returns`false`

if fast is a list node reference. Basically, it's a faster way of writing`if (fast === null) return head.next`

.This line deals with an edge case where, if we go forward

`n`

nodes and find the end of the list, it means that the`n`

th node from the end is actually the very first node. Since the rest of the code assumes that we'll be finding nodes on either side of the target node which can be stitched together, this can cause a problem, as there is no node prior to the start of the list.So the easiest thing to do is just to "remove" it by simply returning the second node of the list as the head of our answer list.

My Java Solution :

github.com/Rohithv07/LeetCodeTopIn...