算法的学习笔记—链表中倒数第 K 个结点(牛客JZ22)

😀前言
在编程过程中，链表是一种常见的数据结构，它能够高效地进行插入和删除操作。然而，遍历链表并找到特定节点是一个典型的挑战，尤其是当我们需要找到链表中倒数第 K 个节点时。本文将详细介绍如何使用双指针技术来解决这个问题，并提供一个基于 Java 的具体实现。

🏠个人主页：尘觉主页

🥰链表中倒数第 K 个结点

牛客网

😄描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤10⁵，0≤a_i≤10⁹，0≤k≤10⁹

要求：空间复杂度 O(n)，时间复杂度 O(n)

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

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

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

😉示例1

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

😉示例2

输入：{2},8
返回值：{}

😀解题思路

解决这个问题的关键在于如何有效地遍历链表，同时保证我们能准确定位倒数第 K 个节点。最常见的方法是使用双指针技巧，即使用两个指针 P1 和 P2 来遍历链表。

1. 初始化双指针： 首先，让指针 P1 向前移动 K 个节点，期间如果 P1 已经到达链表末尾，则表示链表长度不足 K，返回空链表。
2. 同步移动双指针： 当 P1 移动到链表末尾时，指针 P2 开始从链表头同步移动。由于 P1 已经提前移动了 K 个节点，当 P1 到达链表末尾时，P2 正好位于倒数第 K 个节点处。
3. 返回结果： 最终，返回指针 P2 所指向的节点，该节点即为所需的倒数第 K 个节点。

🥰代码实现

下面是基于上述思路的 Java 代码实现：

public class Solution {public ListNode FindKthToTail(ListNode head, int k) {// 如果链表为空，直接返回 nullif (head == null)return null;// 定义两个指针ListNode P1 = head;// 让 P1 先向前移动 K 个节点while (P1 != null && k-- > 0)P1 = P1.next;// 如果 K 还大于 0，说明链表长度小于 Kif (k > 0)return null;// 定义第二个指针 P2ListNode P2 = head;// 同步移动 P1 和 P2，直到 P1 到达链表末尾while (P1 != null) {P1 = P1.next;P2 = P2.next;}// 返回 P2，此时 P2 位于倒数第 K 个节点return P2;}
}

😊 性能分析

该算法的时间复杂度为 O(n)，因为我们需要遍历链表两次：一次用于将 P1 指针移动 K 个节点，另一次用于同步移动 P1 和 P2。空间复杂度为 O(1)，因为我们只使用了固定数量的额外空间，即两个指针。

😄总结

通过使用双指针技术，我们能够高效地找到链表中的倒数第 K 个节点。这种方法不仅简单明了，而且在大多数情况下都能提供良好的性能表现。在处理链表相关问题时，双指针技术是一个非常有用的工具。希望本文的讲解能帮助你更好地理解和解决类似的链表问题。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞