连绵的春雨把人困在家乡，于是我继续开始刷着算法题，通过 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）个节点被移除。
于是算法思路如下：
-
- 通过遍历获得链表长度L1。
-
- 计算出从头部开始数是第（L1 – n）个节点。
-
- 用一个指针从head开始变量到第(L – n – 1)个节点，然后将它的next指向它下一个的下一个节点，完成节点移除。
-
- 然后返回原来的链表的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_lis服务器托管t += 1
current = current.next
pos = length_list - n
# it means that we should remove the first node
if pos 这个方案比较符合人性，也容易想到，但是缺点是必须先遍历一遍整个链表获得链表长度，然后再移动指针到删除的那个节点之前的节点。
有没有办法不先获取链表长度，又能顺利从链表头部移动到想要删除的节点之前呢？我想起了古代小兵探路的故事，可以让一个指针先行一步，探出一条准确的步数，然后再让一个指针走L1（链表长度） – n – 1个节点就行了。
我简单绘制了一张图, 步骤如下所示：
- 定义一个dump节点，它的next指向head，fast和slow都指向dump。
- 用一个fast指针和slow指针分别进行移动，fast指针优遍历前n个节点，那么剩下没遍历的节点数量刚好就是L1 – n。
- 然后再继续遍历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 = h服务器托管ead
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 如下图所示，这个算法的Runtime非常快，但是memory使用就比较大，毕竟用了2个指针以及dump去实现了遍历。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 【网络奇缘】——奈氏准则和香农定理从理论到实践一站式服务|计算机网络
个人主页:Aileen_0v0 热门专栏:华为鸿蒙系统学习|计算机网络|数据结构与算法 个人格言:”没有罗马,那就自己创造罗马~” 目录 失真 – 信号的变化 影响信号失真的因素： 编辑 失真的一种现象：码间串扰 奈氏准则： 奈氏准则概念及使用条件: 奈氏准…
