题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
我的方法：
基本的思路是两次遍历。第一次遍历得到链表的长度l。第二次遍历时删除倒数第n个节点，也就是第l-n+1个节点。
需要特别注意的是，如果n==l，则直接把head节点指向head.next节点。
很快解决了问题，但运行速度太慢。执行用时 : 44 ms, 在Remove Nth Node From End of List的Python提交中击败了4.75% 的用户。内存消耗 : 10.8 MB, 在Remove Nth Node From End of List的Python提交中击败了0.91% 的用户。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
#目前的想法是两趟实现
if head==None:
return
l=0#链表的长度
hd=head#记录链表的头
# 第1趟：得到链表的长度
while head:
head=head.next
l+=1
i=0#索引
head=hd
if n==l:
return head.next
# 第2趟：删除特定节点
while head:
if i==l-n-1:
pre=head
if i==l-n:
pre.next=head.next
head=head.next
i+=1
return hd
别人的方法：
看了参考解法，确实很精妙。方法是使用双指针，其中一个指针先向前运行n步，另一个指针在开头位置。则两个指针之间保持n的距离。使两个指针同时向右移动，当后一个节点到达链表尾端时，前一个指针正好在倒数第n个节点的位置。此时，对前一个指针所对应next节点进行删除操作即可。
代码如下。运行速度果然快了许多：执行用时 : 28 ms, 在Remove Nth Node From End of List的Python提交中击败了99.56% 的用户。内存消耗 : 10.9 MB, 在Remove Nth Node From End of List的Python提交中击败了0.91% 的用户。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
first=head
second=head
# 移动第2个节点至第n个位置
for i in range(n):
second=second.next
if not second:
return first.next
# 同时移动第1和第2个节点
while second.next:
first=first.next
second=second.next
# 删除指定节点
first.next=first.next.next
return head
