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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

进阶：你能尝试使用一趟扫描实现吗？

解题思路：

1. 最简单的方法是先遍历一次链表，得到链表的长度len，然后再一次遍历链表，遍历到第len-n个节点时就是要删除节点的前驱tem:

1. 如果len-n=0,说明要删除的节点是第一个节点，直接return head.next，

2. 否则，tem.next=tem.next.next，然后reutrn head。

但是上面这种方式需要两趟扫描，下面有两种方式可以使用一趟扫描实现

1. 以空间换时间：从前往后遍历一次链表，将每次遍历的节点保存在数组list中。遍历完成之后，就可以得到数组的长度size，那么第index = size-n-1个节点就是要删除节点的前驱

1. 如果index<0；说明要删除第一个节点，直接return head.next

2. 否则，list[index].next=list[index].next.next，然后 return head

AC代码：

class Solution {public static ListNode removeNthFromEnd(ListNode head, int n) {ArrayList<ListNode> list = new ArrayList<>();ListNode ans = head;while (ans != null) {list.add(ans);ans = ans.next;}int size = list.size();int removeIndexBefore = size - n - 1;if (removeIndexBefore < 0) {return head.next;}ListNode removeIndexBeforeNode = list.get(removeIndexBefore);removeIndexBeforeNode.next = removeIndexBeforeNode.next.next;return head;}
}

2. 快慢双指针法：使用两个指针，一个先走，一个后走

1. 让第一个指针first先走n步

1. 如果first==null：说明要删除的节点是第一个节点，直接return head.next

2. 然后第一个指针first和第二个指针second同时走，当first走到最后一个节点时(此时fist.next=null)，那么第二个指针的位置就是要删除节点的前驱,令second.next=second.next.next，然后return head

AC代码

class Solution {public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode first = head;ListNode second = head;for (int i = 0; i < n; i++) {first = first.next;}if (first == null) {return head.next;}while (first.next != null) {first = first.next;second = second.next;}second.next=second.next.next;return head;}
}