多种方法从尾部移除指定位置的链表节点

连绵的春雨把人困在家乡，于是我继续开始刷着算法题，通过 19. Remove 年th 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.     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，是从链表头部开始算位置，那么这道题就非常简单，直接循环遍历到第n个节点，然后把第n个节点之前的节点的next改为第n+1个节点就行了。
但现在却是从尾部开始数n个节点，所以需要做一些处理。

最直接的思路是，把从尾部的问题变成从头部遍历的问题，从尾部开始往前第n个节点，就是从头部往后第（链表长度 - n）个节点被移除。

于是算法思路如下：

• 1. 通过遍历获得链表长度L1。
• 2. 计算出从头部开始数是第（L1 - n）个节点。
• 3. 用一个指针从head开始变量到第(L - n - 1)个节点，然后将它的next指向它下一个的下一个节点，完成节点移除。
• 4. 然后返回原来的链表的head。

用Python实现的代码如下：

class Solution(object):     def removeNthFromEnd(self, head, n):         """         :type head: ListNode         :type n: int         :rtype: ListNode         """         if head.next == None:             return None                  current = head         length_list = 0         while current != None:             length_list += 1             current = current.next          pos = length_list - n          # it means that we should remove the first node         if pos <= 0: return head.next                  # define the pointer to start to iterate the nodes         moving_pointer = head;         for i in range(pos - 1):             moving_pointer = moving_pointer.next           # If the node that we want to remove is not exist, just return the original list         if moving_pointer.next == None:             return head                  # Skip the deleted node         moving_pointer.next = moving_pointer.next.next          return head  

这个方案比较符合人性，也容易想到，但是缺点是必须先遍历一遍整个链表获得链表长度，然后再移动指针到删除的那个节点之前的节点。

有没有办法不先获取链表长度，又能顺利从链表头部移动到想要删除的节点之前呢？我想起了古代小兵探路的故事，可以让一个指针先行一步，探出一条准确的步数，然后再让一个指针走L1（链表长度） - n - 1个节点就行了。

我简单绘制了一张图, 步骤如下所示：

1. 定义一个dump节点，它的next指向head，fast和slow都指向dump。
2. 用一个fast指针和slow指针分别进行移动，fast指针优遍历前n个节点，那么剩下没遍历的节点数量刚好就是L1 - n。
3. 然后再继续遍历fast和slow，就能顺利遍历到第L1 - n -1个节点，然后移除掉下一个节点，然后返回修改后的list。
   

那么想好之后，快速写出代码：

 class Solution(object):    def removeNthFromEnd(self, head, n):         """         :type head: ListNode         :type n: int         :rtype: ListNode         """         dump = ListNode(0)         dump.next = head         fast = dump         slow = dump          for i in range(n+1):             fast = fast.next          # move the fast to the end of the list         while fast != None:             fast = fast.next             slow = slow.next                  if slow.next == None:             return dump.next                  slow.next = slow.next.next          return dump.next  

Js版本类似：

/**  * @param {ListNode} head  * @param {number} n  * @return {ListNode}  */ var removeNthFromEnd = function(head, n) {      let dump = new ListNode(0);     dump.next = head;     let fastPointer = dump;     let slowPointer = dump;      for (let i = 0; i <= n; i++) {         fastPointer = fastPointer.next;     }      while(fastPointer != undefined) {         fastPointer = fastPointer.next;         slowPointer = slowPointer.next;     }      slowPointer.next = slowPointer.next.next;      return dump.next; };  

如下图所示，这个算法的Runtime非常快，但是memory使用就比较大，毕竟用了2个指针以及dump去实现了遍历。