今天直接來看題目的敘述：Given the head of a linked list, remove the nth node from the end of the list and return its head.

也就是我們要從linked list尾端數第n個node並把它移除後，再將它回傳。

我們應該如何下手？

今天題目給的事單向連結串列（single linked list），而非雙向鏈接串列如下圖 （Doubly linked list），雙向鏈接和單向連結的差異主要是雙向可以知道前面和後面的node，所以如果題目給的是雙向鏈結，解題就會相對容易。

那我們現在既然不能直接從後面開始倒過來拜訪node，這裡就要使用我們在解linked list時常用到的技巧 → pointer 兩個指標來追蹤

利用範例Input: head = [1,2,3,4,5], n = 2來說明

1 → 2 → 3 → 4 → 5 → null

我們宣告一個First (F)和Second (S)指標來追蹤

一開始我們把Ｆ和Ｓ指標都放在１身上

然後讓Ｓ走兩步( n = 2)來到 3 變成

1 → 2 → 3 → 4 → 5 → null
^       ^
F       S

然後們讓Ｆ和Ｓ一起往右移動直到Ｓ摸到null為止

來看下面不會動的動畫，看會怎麼樣

			    1 → 2 → 3 → 4 → 5 → null
step1			^       ^
			    F       S
step2                ^       ^
			         F       S
step3                   ^       ^
			            F       S
step4                        ^        ^
			                 F        S

偷看一下leetCode的解答
Output: [1,2,3,5]

有沒有發現現在的F剛好就在我們要移除的4身上！！
然後我們就可以把3的next換成５其實這題就解決了！

不過，我們應該還要還要考慮到

1. 我們根本不知道4的前面是3
   那我們應該怎麼做？
   我們在還可以知道4的前面是3的時候應該是second指標將要移到null的時候，也就是在共同前進的while判斷應該要停止在second.next === null 之前

2. 萬一今天n換成５，一開始走了５步後會變成如下，也就是我們就把頭砍掉即可

   			    1 → 2 → 3 → 4 → 5 → null
   step1			^                    ^
   			    F                    S
   

3. 不要忘記有下面這種情況，

Input: head = [1], n = 1
Output: []

時間複雜度為：Ｏ(n)，空間複雜度：Ｏ(1)

來看最後的實作

var removeNthFromEnd = function (head, n) {
  let step = 1;
  let first = head;
  let second = head;
  // step用來確保我們先移動second的步數
  while (step <= n) {
    second = second.next;
    step++;
  }
  // 考慮情況二
  if (second === null) {
    if (head.next) {
      head.val = head.next.val;
      head.next = head.next.next;
    } else {
		// 考慮情況三
      head = null
    }
    // 做完就沒事了
    return head;
  }
  // 考慮情況一
  while (second.next !== null) {
    second = second.next;
    first = first.next;
  }
  // second.next === null 時直接把first.next換掉
  first.next = first.next.next;
  return head;
};

明日題目預告：再玩一題Linked Lists相關題吧！
Add Two Numbers