题目：给定一串链表和一个整数n，要求删除链表倒数第n个节点 (注:输入的n永远是合法的，试着访问 '一次' 链表就搞定)
如：链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7. 给定n=3，则删除倒数第3个节点，即值为5的节点
思路：
- 如果我们知道链表的长度
length，那么就很好找到倒数第n个节点，也就是正数的第length - n + 1个； - 但是题目中没有给链表长度，我们只能换个思路，我们怎么确定哪个节点在当前链表中是倒数第
n个呢，那么我们正常思维方式是先找到链表的末尾，然后依次向前数：倒数第一个，倒数第二个... 直到倒数第n个，反过来想，如果我们通过指针slow正序遍历找到某个位置的时候，恰好有个指针fast指向链表末尾(因为我们可以通过指针的next为null来确定当前是指向了链表末尾)，而且两个指针正好相差n - 1给位置，那么我们就确定了指针slow指向的正好就是倒数第n个位置的元素，为了更直观的表达，画两个图展示一下，以找到倒数第5个节点为例：
查找倒数第五个节点
代码：
// 自定义节点
class DevNode {
public DevNode() {
}
// 当前节点的值
public int value;
// 当前节点指向的下一个节点
public DevNode next;
}
private DevNode findNodeAt(DevNode head, int n) {
if (head.next == null || n <= 0) {
return null;
}
// 慢指针 指向头节点
DevNode slow = head;
// 快指针 指向头节点
DevNode fast = head;
// 前指针 指向慢指针指向的节点的前一个节点
DevNode pre = head;
// 快指针先走到第n-1个节点
while (--n != 0 && fast.next != null) {
fast = fast.next;
}
// 快慢指针一起走 快指针走向链表末尾则结束
while (fast.next != null) {
fast = fast.next;
pre = slow;
slow = slow.next;
}
// 如果删除的节点是头节点，直接返回头节点指向的下一个节点
if (slow == head) {
return head.next;
}
// 如果删除的是倒数第一个节点，则pre的下一个节点置为null，否则指向slow的next.
// 目的：保持原有链表的结构
pre.next = slow.next == null ? null : slow.next;
return slow;
}
