4. 单链表的倒数第 k 个节点

前提摘要：

从前往后寻找单链表的第 k 个节点很简单，一个 for 循环遍历过去就找到了，但是如何寻找从后往前数的第 k 个节点呢？

那你可能说，假设链表有 n 个节点，倒数第 k 个节点就是正数第 n - k + 1 个节点，不也是一个 for 循环的事儿吗？

是的，但是算法题一般只给你一个 ListNode 头结点代表一条单链表，你不能直接得出这条链表的长度 n，而需要先遍历一遍链表算出 n 的值，然后再遍历链表计算第 n - k + 1 个节点。

也就是说，这个解法需要遍历两次链表才能得到出倒数第 k 个节点。

那么，我们能不能只遍历一次链表，就算出倒数第 k 个节点？可以做到的，如果是面试问到这道题，面试官肯定也是希望你给出只需遍历一次链表的解法。

// 返回链表的倒数第 k 个节点
ListNode findFromEnd (ListNode head, int k) {
    ListNode p 1 = head;
    // p 1 先走 k 步
    For (int i = 0; i < k; i++) {
        P 1 = p 1. Next;
    }
    ListNode p 2 = head;
    // p 1 和 p 2 同时走 n - k 步
    While (p 1 != null) {
        P 2 = p 2. Next;
        P 1 = p 1. Next;
    }
    // p 2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    Return p 2;
}
 

无论遍历一次链表和遍历两次链表的时间复杂度都是 O(N)

很多链表相关的算法题都会用到这个技巧，比如说力扣第 19 题「删除链表的倒数第 N 个结点

没看懂没关系，通过题目来了解下：

解法：

// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
    
private ListNode findFromEnd(ListNode head, int k) {
    // 代码见上文
}
 

可视化动画： 很清晰，跟了一遍后，上面的返回倒数第 K 个节点就悟了

双指针技巧秒杀七道链表题目 | labuladong 的算法笔记

---

Tip

使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。
但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除