题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

方法一：双指针

  1. Definition for singly-linked list.
  2. class ListNode(object):
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.next = None
  7. class Solution(object):
  8.     def removeNthFromEnd(self, head, n):
  9.         """
  10.         :type head: ListNode
  11.         :type n: int
  12.         :rtype: ListNode
  13.         """
  14.         node=ListNode(-1)#新建一个链点
  15.         node.next=head#把新建的链点放到开头
  16.         first=second=node #建立两个指针
  17.         for i in range(n):
  18.             first=first.next #让first前进n个单位
  19.         while first.next: #只要first的后一个不为空
  20.             #first和second同时后移，通过间隔n来解决获得倒数第n的问题
  21.             first=first.next
  22.             second=second.next
  23.         second.next=second.next.next#一个掐断链点的模板  左边比右边少一个next
  24.         return node.next 
  25.         #到此为主，我们终于了解了这个node的作用 
  26.         # 1）用来返回，
  27.         # 2）通过在前面设定一个node，避免后面搞什么n-1之类的循环

这个方法的使用一个哑节点来保持距离。
双指针不仅在数组中使用，在链表中使用双指针也是常识
总结一下在链表中双指针的用法
1）用于追踪节点和替换节点关系
2）用于锁定具有一定距离关系的节点

方法二：递归

  1. class ListNode(object):
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  6. class Solution:
  7.     def removeNthFromEnd(self, head, n):
  8.         global count
  9.         if head is None:
  10.             count=0 #在none的时候记0，因为没有倒数第0
  11.             return None
  12.         head.next=self.removeNthFromEnd(head.next,n)  
  13.         #当count==n时，此句等效于head.next=head.next.next
  14.         count+=1
  15.         return head.next if n==count else head #这里的判读，决定返回的出口

有一段话说得很好
递归其实是两个过程，递和归！
这种解法用一句话形容，就是在递和归重合得时候，把需要去掉得节点去除。
在递归中使用global，否则不能击穿递归块。
怎么理解递归？
我觉得用嵌套的正方形模块进行理解比较好。
还是自己体会吧~

收获与思考

自己看代码，收获都在代码注释和下面得解释中