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:

1. The number of nodes in the list is sz.
2. $$1 \leq sz \leq 30$$.
3. $$0 \leq Node.val \leq 100$$.
4. $$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 n: int
:rtype: ListNode
"""

fast_pos = 0
slow_pos = 0

while fast_pos - slow_pos < n:
fast_node = fast_node.next
fast_pos += 1

# critical part
if fast_node is None:

while fast_node.next:
fast_node = fast_node.next
slow_node = slow_node.next

slow_node.next = slow_node.next.next



#### 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>>



## 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.