# 19. Remove Nth Node From End of List

Note this one

## 1. Description

Given the `head`

of a linked list, remove the `nth`

node from the end of the list and return its head.

Constraints:

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

. - \(1 \leq sz \leq 30\).
- \(0 \leq Node.val \leq 100\).
- \(1 \leq n \leq sz\).

### 1.1. Examples:

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]

## 2. Solution

### 2.1. Understanding the problem

From the provided code we can see it's a singly linked list.

We can use `fast_node`

and `fast_pos`

that will reach the end of the list, and `slow_node`

and `slow_pos`

that will be `n`

node(s) away from `fast_node`

. Slow node will be tracking the previous node of the node to be removed.

Given that the trivial case `[1]`

and `n=1`

returns `[]`

, we have `slow_node = head`

, `slow_pos = 0`

and `fast_node = head`

and `fast_pos = 0`

.

In the end we want to first have `fast_node`

and `slow_node`

to be `n`

nodes away and then move both of them to the next node, until `fast_node`

reaches the end of the list.

**Note that slow_node will be the node that is connected to fast_node, and the node between them will be removed.**

### 2.2. Algorithm

Incorrect algorithm where I put progression of space between `slow_node`

and `fast_node`

by moving `fast_node`

, and `slow_node`

and `fast_node`

moving together, under the same while loop.
In this case I had difficulty handling the edge case with `head`

being the element to be removed via checking if `fast_node is None`

.
I had no way of returning from the `while`

loop.
Once the `while`

loop finishes, I have no way of distinguishing the following situations so I won't know if I need to remove the head:

n = 3

1 | 2 | 3 | None |

s | f |

n = 3

1 | 2 | 3 | 4 | None |

s | f |

1. Initialise ~fast_node = head~, ~fast_pos = 0~, ~slow_node = head~, ~slow_pos = 0~ 2. while ~fast_node.next~ 1. if ~fast_pos - slow_pos < n~ 1. ~fast_node = fast_node.next~, ~fast_pos += 1~ 2. if ~fast_pos - slow_pos == n~ 1. ~fast_node = fast_node.next~, ~fast_pos += 1~ 1. ~slow_node = slow_node.next~, ~slow_pos += 1~

### 2.3. Code

def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ fast_node = head fast_pos = 0 slow_node = head slow_pos = 0 while fast_pos - slow_pos < n: fast_node = fast_node.next fast_pos += 1 # critical part if fast_node is None: return head.next while fast_node.next: fast_node = fast_node.next slow_node = slow_node.next slow_node.next = slow_node.next.next return head

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(N)`

##### 2.3.1.2. Space complexity:

`O(1)`

### 2.4. Leetcode solution

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

I had to check Leetcode solution for this one as my original wasn't right.

I think the hardest part is again the edge cases, especially how to handle a linked list of only one element, although it's not really relevant in this case, and how to remove the head node.