1. 题目描述
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
2. 解题思路
2.1 方法一：两次遍历算法
思路
该问题可以简化：删除从列表开头数起的第 (L - n + 1) 个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。
算法
- 首先我们将添加一个 哑结点（哨兵节点）作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。
- 第一次遍历，我们找出列表的长度 L。
- 第二次遍历，找到要删除的节点，即第 (L - n) 个结点，删除即可。
但是题目要求一次遍历。
2.2 方法二：一次遍历算法
设置前后两个指针，front 和 back，他们之间的间隔是固定的，保持为 n，而后同步往后移动。当 back 指针指向 尾结点之后的 None 时，front 节点刚好指向需要删除节点的前一个节点 ，而后删除即可。详见下面动画。（动画中 p 即 front，q即 back）
2.3 Python代码详解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
s = ListNode(None) # 增加哨兵节点，便于统一对头结点操作 （删除头结点比较方便）
s.next = head
front = s # 前后两个指针，当 back 指针指向 尾结点之后的 None 时，front 节点刚好指向需要删除节点的前一个节点
back = s
for k in range(0, n+1): # 移动 back 指针，使得 front 和back 指针间隔 n 个节点的距离
back = back.next
# print(front, back) # 善于使用 print 进行调试
while (back): # 两个指针同步后移
front = front.next
back = back.next
front.next = front.next.next # 删除节点操作
print(front)
return s.next # 不能返回 head 因为可能头结点都删除掉了！！！
3. 举一反三
关于双指针的用法还有一些经典题目。详见之前的文章如下链接：
【LeetCode】141 环形链表 I，142. 环形链表 II（双指针 中学追及问题）
【LeetCode 】160. 相交链表（双指针法 Python 7行代码 中学追及问题）
京公网安备 11010502036488号