Given a linked list, remove the nth node from the end of list and return its head.
For example,
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.
链表的一道简单题目，题目要求只扫one pass只扫一遍链表，但是通常情况下不知道链表总长度，则无法知道倒数第N个结点（实际考虑的是倒数第N＋1个结点）在哪里。使用是链表中常用的技巧，维护一前一后两个指针fast和slow。fast指针比slow指针先走N步。这样当fast指针指向链表最后一个元素时，slow指针指向的是倒数（N+1）个结点，然后进行删除元素的处理。
值得注意的是：如果删除的是头结点，则在fast先走N步（等于链表长度）之后，fast为None，之后再同时移动fast和slow时，判断fast.next来决定是否已到达尾结点会直接造成访问错误。解决方法有两种：第一种是在fast先走N步时判断fast是否已经为None，为None，则说明删除的是头结点，返回head.next。第二种是增加一个dummy哑元素，fast先走N步之后，即使是删除头元素，也会指向尾结点。防止后序的判断错误，但是这种做法有一个坏处，即是多了辅助元素，并且实际fast和slow都各多走了1步。
方法一代码：
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ fast = slow = head for _ in range(n): fast = fast.next if not fast: return head.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head
方法二代码：
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ if not head: return None dummy = ListNode(-1) dummy.next = head fast = slow = dummy for i in range(n): fast = fast.next while fast.next: slow = slow.next fast = fast.next slow.next = slow.next.next return dummy.next
注意题目本身说到n是合法的，但是在实际面试中这种合理的假设通常不存在，所以需要加入一些合理性判断，判断是否合法,这里事先假设越界时直接返回head。基于第一种解法更改如下：
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ fast = slow = head i = 0 while i < n and fast: fast = fast.next i += 1 if i < n-1: return head if not fast: return head.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head
总结来说：链表需要注意的点为：
1. 越界：容易造成内存访问错误，比如调用了None.next。尤其对于空链表的特殊情况。
2. 更新head的特殊处理
3. 删除节点时没有保留下一个移动位置的指针（多用于reverse linked list）。
4. 移动位置存在+-1的偏差。
常用技巧：
1. Dummy head：简化改变、删除头指针的处理。
2. 前后双指针：多用于链表反转。
递归解法，值得注意：
class Solution: def removeNthFromEnd(self, head, n): def remove(head): if not head: return 0, head i, head.next = remove(head.next) return i+1, (head, head.next)[i+1 == n] return remove(head)[1]