LeetCode_19删除链表的倒数第N个结点

LeetCode_19

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
方法
只使用一次遍历,使用两个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n个结点分开。通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。而要删除的目标元素就是第二个指针指向的下一个结点。
难点
1、 ListNode dummy = new ListNode(0);//先虚设链表头节点前面有一个位置(增加一个初始位置)，可以用来标记寻找第一个结点，也可以存放两个指针。
2、second.next = second.next.next;//如果first移n+1后指向空，则second指针移动后的下一个元素为目标元素跳过即为删除
图解分析

代码实现

复杂度分析
时间复杂度：O(L)，
此算法对含有 L 个结点的列表进行了一次遍历。因此时间复杂度为O(L)。
空间复杂度：O(1)，
只用了常量级的额外空间。