# 19. Remove Nth Node From End of List
###### tags: `Python`,`Leetcode`
## MyCode!
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
### Way 1

### Way 2

## 解題思路
### Way 1
* 題目要求移除 Linked List 從尾巴數的第 n 個 node，但 Linked List 須逐步指到下一個 node 無法用 index 取出
* 所以我使用了四個變數：
1. count
2. count2
3. head1
4. head2
第一、三個變數用於得知 List 究竟有多長
第二、四個變數用於實際得知從尾巴數來第 n 個 node，且第四個變數將會做為回傳的 Linked List head
* Linked List 只能從頭數到尾巴，運用 count = count - n ，就會變成「從前面數來的第『 count 』個 node 就是題目要求移除的 node 」，但是要注意有幾個可能：
1. 前情提要 count - n 所得的數字會比欲移除的數字少 1
2. 所以如果 count - n = 0，表示要刪掉的是第一個 node，把 head 改為「第一個 node 的 next」，return 新的 head 後，扯出後面的料
3. 如果 count == 1，表示要刪掉的 node 是第二顆，此時要把第一顆 node 的 pointer 指到第三顆
4. 其他狀況是確定要　remove 的 node 後，把 node - 1 的 pointer 指向 node + 1
### Way 2 (Teddy Codes)
* 使用三個變數：
1. count (用來數 node 用)
2. list_head ( Linked List 的 head )
3. idx (用來找到要刪掉的 node )

## 解法
### Way 1
#### Step 1 : 設四個變數
* 第一、三個變數用於得知 List 究竟有多長
* 第二、四個變數用於實際得知從尾巴數來第 n 個 node，且第四個變數將會做為回傳的 Linked List head
1. count = 0 (運用來得知整個 List 多長，希望得出「從前面數來的第『 count 』個 node 就是題目要求移除的 node 」)
2. count2 =1 (運用來從頭開始算，等於 1 的原因位於 Step 2)
3. head1 = head
4. head2 = head
#### Step 2 : 使用 head 、 count 跑一個 while 迴圈，確定未刪除 node 前 List 的長度
* 當每推進一個 next， count 就會加 1，推到沒有 next 時，加 1 會停止，所以 count - n 所得的數字會比欲移除的 node index 少 1 (因為尾巴的 index 少算到)
1. 所以我將缺少的 1 補在 count2
2. 用 count 得知歷經幾個 next，並藉此知道 List 的長度
#### Step 3 : Step 2 迴圈跑完後可以得知整個 List 有多長(length = count)， count = count - n 可得出從頭開始算，我們要刪掉的 node
* 如果一開始 count = 0，表示第一個就是要刪掉的 node ， 直接 return head2.next，就是答案
* 如果一開始 count = 1 ，表示要刪掉的 node 是第二個，把第一個的 node pointer 指向第三個 node （意思就是要略過第二個 node 去刪除他 ）
* 如果是以上兩個狀況，這個回圈就結束了。但其他的狀況就是要不斷推進 node 直到遇到要被刪除的第 count 個 node：
1. 當 count2 == count 時表示找到要刪的 node
2. 把 pointer 指到下下個即可！
3. return head2 結束
### Way 2
#### Step 1 : 使用 while 迴圈與 count 得知 Linked List 有多長
* 設定兩個變數：
1. list_head 是第一個 node 從 head 開始的 Linked List(在迴圈外)
2. count，每推進一個 node，count 就會 +1，用於計算 Linked List 有多長
#### Step 2 : 如果題目指定的 n (從尾巴數來的第 n 個)，跟 count 相同：
* 代表要消掉的是第一個 node，直接把第二個 node 叫出來，隨之而來就會扯出後面的料
#### Step 3 : 把 list_head 歸回 head （重頭開始），並且 count 更新為 count - n(如此從頭開始數的第 count 個會是我們要刪除的 node)
#### Step 4 : 用 while loop,idx 這個變數慢慢指 node，指到第 count 個，就是我們要刪掉的
* 於是就把第 count 的 node pointer 指向下下個 node （忽略下個 node 跳到下下個 = 刪除下個）
#### Step 5： return head
* 輸出 head 而不是 list_head 的原因：
1. 因為 list_head 跟 head 使用同一塊記憶體，故刪除、增加都會一起加加減減
2. **return head 是因為只有這個 node 是第一個，list_head 此時的位置已經到了第 count 的位置，return 出來會錯**