19. Remove Nth Node From End of List
题目描述：
Given a linked list, remove the nth node from the end of list and return its head.
Example 1:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
- Given n will always be valid.
- Try to do this in one pass.
题目翻译
给定一个排好序的链表，删除从后往前数的第n个节点并且返回删除后的链表头指针。
示例1：
给定的链表：1->2->3->4->5，n = 2
删除倒数第2个节点后的链表：1->2->3->5
注意：
- 给定的链表总是正确的
- 在一次遍历中完成操作
解题方案
标签： Linked List
思路：
- 本题需要维护两个指针，pre和end。一开始初始化时使得pre指针指向链表头节点，end指针指向pre+n的节点位置。然后同时往后移动pre和end指针位置，使得end指针指向最后一个节点，那么pre指针指向的则是end-n的节点位置（即倒数第n个元素的前一个节点），则将其删除。
- 链表长度为n时，算法复杂度O(n)。
代码：
# 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
"""
pre = head
end = head
for _ in range(n):
end = end.next
if end is None: # 需要删除的节点为第一个节点时，即返回第二个节点为头节点的链表
return head.next
while end.next is not None:
pre = pre.next
end = end.next
pre.next = pre.next.next
return head