题⽬描述

输⼊⼀个链表，输出该链表中倒数第k个结点。

例如输⼊{1,2,3,4,5} , 2 时，对应的链表结构如下图所示：

其中蓝⾊部分为该链表的最后2 个结点，所以返回倒数第2 个结点（也即结点值为4 的结点）即可，系统会打印后⾯所有的节点来⽐较。

示例1
输⼊：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后⾯所有的节点来⽐较。

示例2
输⼊：{2},8
返回值：{}

思路及解答

两次遍历法

1. 第一次遍历计算链表长度n
2. 第二次遍历到第n-K+1个节点（即倒数第K个节点）
3. 如果K大于链表长度，返回null

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k  length) return null;
    
    // 第二次遍历找到目标节点
    current = head;
    for (int i = 0; i 

• 时间复杂度​：O(n)，需要遍历链表两次
• ​空间复杂度​：O(1)，只使用了固定数量的指针

双指针法（推荐）

快慢双指针，先让第1 个指针先⾛k 步，然后第2 个指针开始⾛，⽽且两个指针⼀起⾛，直到第⼀个指针⾛到最后的位置。

1. 使用快慢两个指针，快指针先移动K步
2. 然后两个指针同步移动，当快指针到达末尾时，慢指针正好指向倒数第K个节点
3. 如果快指针在移动K步前到达末尾，说明K大于链表长度

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k 

• 时间复杂度​：O(n)，只需遍历链表一次
• ​空间复杂度​：O(1)，使用了两个指针

栈辅助法（空间换时间）

1. 将所有节点压入栈
2. 弹出K个节点，最后一个弹出的即为所求
3. 如果栈中节点不足K个，返回null

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k  stack = new Stack();
    ListNode current = head;
    
    // 所有节点入栈
    while (current != null) {
        stack.push(current);
        current = current.next;
    }
    
    // 检查k是否有效
    if (k > stack.size()) return null;
    
    // 弹出k个节点
    ListNode result = null;
    for (int i = 0; i 

• 时间复杂度​：O(n)，需要遍历链表两次（入栈和出栈）
• ​空间复杂度​：O(n)，需要额外栈空间存储所有节点

递归回溯法

1. 递归遍历到链表末尾
2. 回溯时计数，当计数等于K时返回当前节点
3. 使用全局变量或包装类传递计数

private int count = 0;

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null) return null;
    
    ListNode node = getKthFromEnd(head.next, k);
    count++;
    
    if (count == k) {
        return head;
    }
    return node;
}

• 时间复杂度​：O(n)，需要完整遍历链表
• ​空间复杂度​：O(n)，递归栈空间开销

方法对比与总结

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top