image.png
1. 总结
快慢指针法：
删除倒数第n个元素，若只遍历一次，那么需要两个指针，当“快指针”指向倒数第一个元素时，“慢指针”指向倒数第n+1个元素（相对相差n个位置）。
- 当慢指针指向倒数第n+1个元素时，可以删除倒数第n个元素；
极端情况：当链表长度为n个时，倒数第n个节点的位置，即第一个节点
链表长度为n个，快指针移动n步，“快指针”指向null节点。通过fast==null可以判断出极端情况。可以直接删除头节点。
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
/**
*
* 1,2,null
* f
* s
* 要删除下一个节点，则需要持有到上一个节点
* 快慢指针：
* 1. 快指针走到最后，可能要删除第一个元素；
* 2. 快指针和慢指针相差n步，当快指针指向最后一个元素时，此时慢指针即为倒数第n+1个节点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
/**
* 快指针，先走n步
*/
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
/**
* 当需要删除倒数第n个元素时，指针坐标应该指向倒数第n+1个
* 即获取相对位置。
*
*/
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
