19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
______________________________________________________________________________________________________
这题有很多种方法，
两趟扫描的方法:第一趟得到链表的长度，第二趟直接找倒数第n个，时间复杂度O(n)
一趟的算法有用数组保存这个链表O(n)，然后O(1)复杂度查找删除,但是细细比较比两趟算法时间复杂度要少一个n，但是空间复杂度为O(n)，用空间换时间。
还有一种一趟的算法，类似于双指针的思路，不过这次是三指针，还添加了一个空的头节点，让所有的情形都能一般化。
func removeNthFromEnd(head *ListNode, n int) *ListNode { //加一个头节点给这个链表： resHead := &ListNode{0,head} //del是真正要删除的节点 del := resHead.Next //target倒数第一节点的位置 target := resHead //bre永远在del前一个节点处 bre := resHead for i:=0;i<=n && target != nil; i++ { target = target.Next } for target != nil { target = target.Next del = del.Next bre = bre.Next } bre.Next = del.Next return resHead.Next }
