Day 16 : Remove Nth Node From End of List

今天直接来看题目的叙述：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