算法分享第4题

题目：给定一串链表和一个整数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;
}