題目敘述
題目會給定我們一個串列，和一個n值，要求我們刪除尾巴數來的第n個節點。
例如1->2->3->4->5 和 給定n值=2，要求我們刪除尾巴數來的第2個節點。
尾巴數來的第2個節點是4，刪除之後，更新連結，輸出答案如下
1->2->3->5
測試範例
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
演算法:
使用雙指針演算法，一個快指針，一個慢指針。
快指針提早領先出發n步，接著慢指針和快指針再一起往前移動。
當快指針抵達終點時，慢指針會剛好指向尾巴數來第n個節點的前一個位置。
註:
為什麼要尾巴數來第n個節點前一個位置?
因為不僅僅是刪除而已，還要更新連結 node.next
程式碼
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# use dummy head will make the removal of head node easier
dummy_head = ListNode(-1)
dummy_head.next = head
# cur keeps iteration till the end
# prev_of_removal traverses to the previous node of the one of being removed
cur, prev_of_removal = dummy_head, dummy_head
while cur.next != None:
# n-step delay for prev_of_removal
if n <= 0:
prev_of_removal = prev_of_removal.next
cur = cur.next
n -=1
# Remove the N-th node from end of list
n_th_node = prev_of_removal.next
prev_of_removal.next = n_th_node.next
del n_th_node
return dummy_head.next
複雜度分析
時間複雜度: O( n )
從左到右，把整個串列掃描一遍。
空間複雜度: O( 1 )
用到一組雙指針，指針所占用的空間大小都是固定的，為常數級別O(1)。
關鍵知識點
在於畫圖觀察規律，想到用快、慢雙指針，快指針領先慢指針n步，定位尾巴數來第n個節點的演算法。
Reference:
