题⽬描述

输⼊⼀个链表，输出该链表中倒数第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

  • 时间复杂度​：O(n)，需要遍历链表两次

  • ​空间复杂度​：O(1)，只使用了固定数量的指针

双指针法（推荐）

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

  1. 使用快慢两个指针，快指针先移动K步

  2. 然后两个指针同步移动，当快指针到达末尾时，慢指针正好指向倒数第K个节点

  3. 如果快指针在移动K步前到达末尾，说明K大于链表长度

  • 时间复杂度​：O(n)，只需遍历链表一次

  • ​空间复杂度​：O(1)，使用了两个指针

栈辅助法（空间换时间）

  1. 将所有节点压入栈

  2. 弹出K个节点，最后一个弹出的即为所求

  3. 如果栈中节点不足K个，返回null

  • 时间复杂度​：O(n)，需要遍历链表两次（入栈和出栈）

  • ​空间复杂度​：O(n)，需要额外栈空间存储所有节点

递归回溯法

  1. 递归遍历到链表末尾

  2. 回溯时计数，当计数等于K时返回当前节点

  3. 使用全局变量或包装类传递计数

  • 时间复杂度​：O(n)，需要完整遍历链表

  • ​空间复杂度​：O(n)，递归栈空间开销

方法对比与总结

方法时间复杂度空间复杂度优点缺点两次遍历法O(n)O(1)实现简单需要两次遍历双指针法O(n)O(1)一次遍历，效率高边界条件需仔细处理栈辅助法O(n)O(n)实现直观空间开销大递归回溯法O(n)O(n)展示递归思想空间效率低