固定间距双指针

固定间距双指针是链表问题中双指针技巧的一种典型应用。它通过先让两个指针建立固定间距，再让它们一起移动，利用它们之间的位置关系来解决一些链表问题。

返回倒数第 k 个节点

面试题 02.02. 返回倒数第 k 个节点

假设链表的长度为 n，我们从链表尾部开始依次编号：最后一个节点为倒数第 1 个节点，往前一个节点为倒数第 2 个节点，依此类推，头节点为倒数第 n 个节点。如图：

一个容易想到的思路是：先求得链表长度 n。然后，我们再来找一下倒数编号与移动步数之间的关系：

• 倒数第 n 个节点移动 0 步；
• 倒数第 n - 1 个节点移动 1 步；
• 倒数第 n - 2 个节点移动 2 步；
• ...

由此可以发现：$链表长度 - 倒数编号$ ，就是我们需要移动的步数！

复盘一下这个方案，我们不难发现：此方案需要遍历两遍链表，分别在求链表长度和找到倒数第 k 个节点各遍历一次。

其实，本题还有一种只需遍历一趟链表的解法。我们换个角度重新思考这个问题。

换个角度来看，倒数编号其实表示从当前节点出发，沿着 next 走到 null 所需的步数：

假设你在一条不知道长度的直线跑道上行走，现在我需要你在距离终点 k 个单位的位置停下来。你认为你能做到么？

显然这是做不到的，毕竟你不知道终点在哪。

现在，我再给你安排一个帮手作为参照。你们两个要怎么走，才能完成这个任务呢？

如果让你的帮手先走 k 个单位，然后你们再一起前进，那么你们之间就会始终保持 k 个单位的间距。

当我宣布你的帮手到达终点时，你不就恰好停在距离终点 k 个单位的位置了么？

现在回到链表中。

我们可以让一个指针 p 先从 head 出发，向前移动 k 步，然后再让另一个指针 q 从 head 出发。

接下来，两个指针每次都向前移动一步，直到 p 到达 null。

此时，q 所在的节点，就是我们要找的倒数第 k 个节点。

基于上述思路，我们不难写出如下代码：

▼
java
复制代码
public int kthToLast(ListNode head, int k) {
    ListNode p = head, q = head;
    for (int i = 0; i < k; i++) {
        p = p.next;
    }
    while (p != null) {
        p = p.next;
        q = q.next;
    }
    return q.val;
}

上述操作只需遍历一趟链表，因此时间复杂度为 $O(n)$。

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

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

相信有了前一题的基础后，这一题对你来说就不成问题了。接下来我就简单说说大致思路即可。

删除某个节点，需要找到它的前驱节点。 然而，头节点没有前驱节点。为了避免单独处理删除头节点的特殊情况，我们引入 dummyNode 作为虚拟头节点。这样，原链表中的每个节点都有前驱节点，删除操作也就可以统一处理了。

接下来，我们只需要找到倒数第 N + 1 个节点，就能删除倒数第 N 个节点。

这里需要注意：当要删除的节点是原链表的头节点时，它的前驱节点正好是 dummyNode。因此，我们需要将 dummyNode 也纳入倒数编号，才能统一处理这种情况。

有了上一题的核心思路，我们不难写出如下代码：

▼
java
复制代码
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head);
    ListNode p = dummy, q = dummy;
    for (int i = 0; i < n + 1; i++) {
        p = p.next;
    }
    while (p != null) {
        p = p.next;
        q = q.next;
    }
    q.next = q.next.next;
    return dummy.next;
}

上述操作只需遍历一趟链表，因此时间复杂度为 $O(n)$。