给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
双指针法：
由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和second 之间间隔了 n?1 个节点，即 first 比second 超前了 n 个节点。
在这之后，我们同时使用 first 和second 对链表进行遍历。当 first 遍历到链表的末尾（即first 为空指针）时，second 恰好指向倒数第 n 个节点。
如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将second 指向哑节点，其余的操作步骤不变。这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。
Python版：
class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0, head) first = head second = dummy for i in range(n): first = first.next while first: first = first.next second = second.next second.next = second.next.next return dummy.next
Java版：
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; ++i) { first = first.next; } while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; ListNode ans = dummy.next; return ans; } }
参考资料：
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)
删除链表的倒数第N个节点 - 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)