leetcode：删除链表的倒数第N个节点

s双指针

想象有一把长度固定的尺子，左端点在链表头部，右端点在正数第 n 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 n 个节点。

由于需要删除节点，我们需要找倒数第 n 个节点的前一个节点（倒数第 n+1 个节点），这样才能做删除操作。

修改：左端点在链表头部，右端点在正数第 n+1 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 n+1 个节点。

细节：如果 n 等于链表长度呢？没有正数第 n+1 个节点。难道要特判这种情况？

不需要。我们可以在头节点的前面插入一个哨兵节点（dummy node），把它当作链表的头节点，这样就有正数第 n+1 个节点了。换句话说，如果遇到需要删除头节点的题目，添加哨兵节点可以简化代码逻辑，请记住这个技巧。

具体请看视频讲解：【基础算法精讲 08】，制作不易，欢迎点赞关注~

答疑
问：前后指针的做法为什么算作「一次遍历」？链表节点不是会被遍历两次吗？

答：链表节点是会被遍历两次。其实我觉得这题本质上想考察的是，在不知道链表长度的前提下，设计一个算法，在「到达链表末尾的瞬间」就能知道倒数第 n 个节点。

问：一般在做链表题时，什么时候要写 while node，什么时候要写 while node.next？

答：如果要遍历到最后一个节点，需要写 while node；如果要遍历到倒数第二个节点，需要写 while node.next。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 由于可能会删除链表头部，用哨兵节点简化代码
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = dummy;
        while (n-- > 0) {
            right = right.next; // 右指针先向右走 n 步
        }
        while (right.next != null) {
            left = left.next;
            right = right.next; // 左右指针一起走
        }
        left.next = left.next.next; // 左指针的下一个节点就是倒数第 n 个节点
        return dummy.next;
    }
}

要解决“从链表末尾删除第 n 个节点”的问题，并且要求使用 反转两次链表 的方法，我们可以按照以下步骤进行：

---

✅ 解题思路

1. 第一次反转链表
   将原链表反转。这样，原链表的倒数第 n 个节点就变成了正数第 n 个节点。
2. 删除反转后的第 n 个节点
   利用哑节点（dummy node）处理头节点被删除的情况，确保删除操作不会出错。
3. 第二次反转链表
   再次反转链表，将删除后的链表还原回原来的顺序。

---

🧠 关键点说明

• 为什么反转两次？
  反转链表后，原本难以定位的倒数第 n 个节点就变成了易于访问的正数第 n 个节点。删除后，再反转回来即可得到最终结果。
• 如何删除第 n 个节点？
  使用哑节点 dummy 来统一处理头节点被删除的情况，然后通过移动指针找到第 n 个节点并删除。
• 反转链表的标准写法
  反转链表时必须确保每个节点都被处理，因此循环条件应为 cur != null，而不是 cur.next != null。

---

🧩 示例代码（Java）

java

深色版本

/**
 * Definition for singly-linked list.
 * 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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 第一步：反转链表
        ListNode reversedHead = reverseList(head);
        
        // 第二步：删除反转后的链表中第n个节点
        ListNode dummy = new ListNode(0);
        dummy.next = reversedHead;
        ListNode prev = dummy;
        ListNode current = reversedHead;

        for (int i = 0; i < n - 1 && current != null; i++) {
            prev = prev.next;
            current = current.next;
        }

        // 删除第n个节点
        prev.next = current.next;

        // 第三步：再次反转链表，恢复原顺序
        ListNode newHead = reverseList(dummy.next);

        return newHead;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

---

🧪 示例说明

假设输入链表为 1 -> 2 -> 3 -> 4 -> 5，n = 2：

1. 第一次反转：链表变成 5 -> 4 -> 3 -> 2 -> 1。
2. 删除第2个节点：删除 4，得到 5 -> 3 -> 2 -> 1。
3. 第二次反转：链表还原为 1 -> 2 -> 3 -> 5。