题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
解答
方案1：走两趟
- 首先从头到尾遍历链表，统计输入链表的长度list_len；
- 计算要删除的节点位置，处理特殊情况，如输入节点为空，要删除的节点位置为0或负数等；
- 把删除倒数第N个节点转变成删除正数第list_len-N个节点的问题，从头到尾遍历链表，并删除指定位置元素；
我们这里删除链表使用语句node.next = node.next.next即可删除原先node.next位置的元素，代码如下：
class Solution:
def removeNthFromEnd(self, head, n):
"""
解决思路：走两趟
:param head:
:param n:
:return:
"""
def get_len(head): # 获取一个链表的长度
n = 0
while head:
n += 1
head = head.next
return n
list_len = get_len(head)
if list_len == 0: # 输入是个空链表
return
node_to_delete = list_len - n # 要删除的节点的位置
if node_to_delete == 0:
return head.next
elif node_to_delete < 0:
return head
else:
# 将倒数第n个转换为正数第cur_len - n个。
i = 0
cur_node = head
while cur_node:
if i == node_to_delete - 1: # 遇到了要删除的结点的前一个结点
cur_node.next = cur_node.next.next # 删除要删除的结点
else:
cur_node = cur_node.next # 当前指针后移
i += 1
return head # 返回链表头结点
执行用时 : 56 ms, 在Remove Nth Node From End of List的Python3提交中击败了80.63% 的用户
内存消耗 : 13 MB, 在Remove Nth Node From End of List的Python3提交中击败了93.66% 的用户
（其实这个性能波动有时挺大）
方案2：快慢指针
我们定义两个指针，快指针和慢指针，让快指针先于慢指针走N步，然后两指针同步向后走，当快指针遍历到链表末尾时，删除慢指针后的元素即可。
class Solution:
def removeNthFromEnd(self, head, n):
"""
解决思路：双指针法
:param head:
:param n:
:return:
"""
pre_head = ListNode(0) # 定义一个临时节点
pre_head.next = head # 将链表挂在临时节点上，临时节点成为头节点
slw = fst = pre_head # 快慢指针开始位置都是临时节点
i = 0
while i <= n and fst: # 快指针提前走n+1步，走到原链表第n个位置
fst = fst.next
i += 1
while fst: # 快慢指针同时走，直到快指针走到链表末尾
fst = fst.next
slw = slw.next
slw.next = slw.next.next # 把慢指针的下一个节点（倒数第n个节点）删除
return pre_head.next
如有疑问或建议，欢迎评论区留言~
