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

date created	date modified
2022-09-10, 12:12:58	2022-09-10, 12:13:00

Meta

• alias:
• parent :: [[algo-删除链表中的元素]]
• siblings ::
• child ::
• refs: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

---

此题的关键是前探针的使用方法。

Class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 单链表，要删除某节点，需拿到指向前序节点的指针
        // 删除倒数第 N 个节点需要找到倒数第 N+1 个节点
        // 前探针指向链表末位 null 时，cur 指向倒数第 N+1 个节点
        // null 为倒数第 0 个节点，往回走 x(x=n+1) 步到达倒数第 N+1 个节点
        // x 即为前探针从 head 开始提前走的步数
        
        // 若要删除 head 节点（即链表只有一个节点，n=1 的情况），添加 dummy 节点更方便
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        // p 提前走 x 步 x=n+1
        for (int i = 0; i < n + 1; i++) {
            p = p.next;
        }
        ListNode cur = dummy;
        while (p != null) {
            cur = cur.next;
            p = p.next;
        }
        // 此时 cur 指向倒数第 N+1 个节点
        cur.next = cur.next.next;
        return dummy.next;
    }
}