https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

题面

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

## 思路① 快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 新建一个虚拟头节点指向head
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    // 快慢指针指向虚拟头节点
    ListNode fastIndex = dummyNode;
    ListNode slowIndex = dummyNode;
    
    // 只要快慢指针相差 n 个节点即可（也就是走 n+1 步）
    for (int i = 0; i < n; i++) {
        fastIndex = fastIndex.next;
    }
    
    while (fastIndex != null) {
        fastIndex = fastIndex.next;
        slowIndex = slowIndex.next;
    }
    
    // 此时 slowIndex 的位置就是待删除元素的前一个位置。
    // 检查 slowIndex.next 是否为 null，避免空指针异常
    if (slowIndex.next != null) {
        slowIndex.next = slowIndex.next.next;
    }
    return dummyNode.next;
}