Question
Given a linked list, remove the nth node from the end of list and return its head.
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.
Notes:
Given n will always be valid.
Try to do this in one pass.
Thinking
定义两个指针，p1,p2.
p1 从头指向尾，p2指向我们需要删除元素的前一个元素。p1 先出发，一直到领先p2 n 个元素的时候，这个时候p2出发，等到p1到达最后一个位置的时候，p2的位置就是我们要删除元素的前一个元素。
注意
p1的初始位置就是head,p2的初始位置则是head的前一个元素，head前一个元素？对，这个时候需要自己定义一个头结点之前的一个node,这样会带来一些方便（还有一些麻烦）
Codes
# 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
"""
p1 = head
p2 = ListNode('#')
p2.next = head
cnt = 1
while p1.next is not None:
p1 = p1.next
if cnt >= n:
p2 = p2.next
cnt += 1
# now p2 is the pre-node of the node to delete
tmp = p2.next
if tmp is None:
pass
else:
p2.next = tmp.next
if tmp == head: # mark1
head = head.next # mark2
del tmp
return head
Key Points
在python 中del是删不掉真正的数据的，删除的只是这个数据的某一个引用。所以如果要删除的元素恰恰是head的话（比如说([1],1)这个输入，不加mark1 , mark2的代码的话返回的结果就是1,但是我们需要的肯定是[]）解决的方法是我们可以进行一下判断，如果p2(待删除元素的上一个元素).next == head，那么就设置head = head.next，因为最后返回的引用是head，所以对del tmp对head并没有什么影响。
这里注意python的del与C++ 的delete完全不一样，delete是删除内存，del只是将一个元素的引用清理掉，怎么进行内存清理时Python解释器的事情。
Performance
好像每一次都不一样？python 大法好....
