双指针在链表中辅助定位

19.题目链接-来源：力扣（LeetCode）

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

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

思路：

我们考虑一趟扫描的思路。思考这样一种实现，我们用两个指针指向链表中的节点，这两个指针之间间隔 n 个结点，我们记更接近尾部的这个指针为 helper，更接近头部的这个指针为 handle，则当 helper 指针达到链表尾部时，handle 恰指向链表的倒数第 n + 1 个节点。
细节：链表题目为了简化判定逻辑，需要在链表头部插入一个辅助性质的「伪头结点」，方便我们简化对空表的判断逻辑。注意我们的 handle 要指向倒数第 n + 1 个节点而非倒数第 n 个节点，这样才能方便我们进行删除操作。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode handle = preHead, helper = preHead;
        int i = 0;
        while (i < n && helper != null) {
            helper = helper.next;
            i++;
        }
        while (helper.next != null) {
            handle = handle.next;
            helper = helper.next;
        }
        handle.next = handle.next.next;
        return preHead.next;
    }
}