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

✨核心逻辑

本题提供两种解决思路：

思路一：常规长度遍历法（两遍遍历）

虚拟头节点：为了方便统一处理（尤其是当删除头节点时），创建虚拟头节点 dummy 指向 head。
获取链表长度：首先遍历一遍原链表，计算出链表的总长度 length。
定位前驱节点：要删除倒数第 n 个节点，等价于删除正数第 length - n + 1 个节点。我们需要找到它的前驱节点（即正数第 length - n 个节点）。
断链删除：将前驱节点的 next 指向下下个节点，完成删除。 断链删除：将慢指针的 next 指向下下个节点，完成删除。

🔥代码实现（含详细变量注释）

public class removeNthFromEnd_19 {
    
    // ================= 思路 1：常规长度遍历法 =================
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // dummy：虚拟头节点，值为 0，其 next 指向原链表的头节点
        // 使用 dummy 节点可以避免单独处理删除头节点的特殊情况
        ListNode dummy = new ListNode(0, head); 
        // copy：用于遍历计算长度的辅助指针，初始指向原头节点 head
        ListNode copy = head;
        
        // length：记录链表的总节点数
        int length = 0;
        while (copy != null) {
            copy = copy.next;
            length++;
        }
        
        // forCopy：用于定位目标节点的前驱节点，从虚拟头节点 dummy 开始
        ListNode forCopy = dummy;
        // 我们需要走到正数第 (length - n) 个节点处，也就是待删除节点的前一个节点
        for (int i = 0; i < length - n; i++) {
            forCopy = forCopy.next;
        }
        
        // n1：此时 forCopy 的下一个节点即为待删除的目标节点
        ListNode n1 = forCopy.next;
        // 执行删除操作：将前驱节点的 next 指针直接跳过目标节点，指向目标节点的 next
        forCopy.next = n1.next;
        
        // 返回 dummy 的下一个节点，即处理后的链表头节点
        return dummy.next;
    }

⏱️复杂度分析----思路一（常规长度遍历)
- 时间复杂度：O(N)，其中 N 是链表的长度。需要遍历两次链表，一次获取长度，一次定位删除位置。
- 空间复杂度：O(1)，只使用了 dummy、copy、forCopy、n1、length 等常数个额外指针和变量。

思路二：快慢指针法（一次遍历）

虚拟头节点：同样建立虚拟头节点 dummy。
快指针先行：让快指针 fast 先走 n 步。
同步前进：当 fast 走完 n 步后，让快指针 fast 和慢指针 slow 同时开始向前移动。
定位前驱节点：当快指针 fast 遍历到链表末尾（null）时，慢指针 slow 正好停留在待删除节点的前驱节点上。
断链删除：将慢指针的 next 指向下下个节点，完成删除。


// ================= 思路 2：快慢指针法（优化空间，一次遍历） =================
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // dummy：虚拟头节点，连接原链表，用于简化头节点的删除操作
        ListNode dummy = new ListNode(0, head);
        
        // fast：快指针，初始指向虚拟头节点 dummy
        ListNode fast = dummy;
        // slow：慢指针，初始指向虚拟头节点 dummy
        ListNode slow = dummy;
        
        // 让快指针 fast 先向前走 n 步（对应要删除倒数第 n 个节点）
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // 当快指针 fast 未到达链表末尾（不为 null）时，快慢指针同步向后移动
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 循环结束时，fast 指向 null（链表末尾之后的空节点），
        // 而 slow 恰好指向了倒数第 n 个节点的**前驱节点**
        
        // 删除操作：将慢指针的 next 跳过目标节点，指向下下个节点
        slow.next = slow.next.next;
        
        // 返回虚拟头节点的下一个节点，即最终的链表头
        return dummy.next;
    }
}