算法的学习笔记—链表中倒数第 K 个结点(牛客JZ22)
😀前言
在编程过程中,链表是一种常见的数据结构,它能够高效地进行插入和删除操作。然而,遍历链表并找到特定节点是一个典型的挑战,尤其是当我们需要找到链表中倒数第 K 个节点时。本文将详细介绍如何使用双指针技术来解决这个问题,并提供一个基于 Java 的具体实现。
🥰链表中倒数第 K 个结点
😄描述
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。如果该链表长度小于k,请返回一个长度为 0 的链表。
数据范围:0≤n≤10^5^,0≤a~i~≤10^9^,0≤k≤10^9^
要求:空间复杂度 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
返回值:{}
😀解题思路
设链表的长度为 N。设置两个指针 P1 和 P2,先让 P1 移动 K 个节点,则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到第 N - K 个节点处,该位置就是倒数第 K 个节点。
😀解题思路2
解决这个问题的关键在于如何有效地遍历链表,同时保证我们能准确定位倒数第 K 个节点。最常见的方法是使用双指针技巧,即使用两个指针 P1
和 P2
来遍历链表。
- 初始化双指针: 首先,让指针
P1
向前移动 K 个节点,期间如果P1
已经到达链表末尾,则表示链表长度不足 K,返回空链表。 - 同步移动双指针: 当
P1
移动到链表末尾时,指针P2
开始从链表头同步移动。由于P1
已经提前移动了 K 个节点,当P1
到达链表末尾时,P2
正好位于倒数第 K 个节点处。 - 返回结果: 最终,返回指针
P2
所指向的节点,该节点即为所需的倒数第 K 个节点。
🥰代码实现
下面是基于上述思路的 Java 代码实现:
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
// 如果链表为空,直接返回 null
if (head == null)
return null;
// 定义两个指针
ListNode P1 = head;
// 让 P1 先向前移动 K 个节点
while (P1 != null && k-- > 0)
P1 = P1.next;
// 如果 K 还大于 0,说明链表长度小于 K
if (k > 0)
return null;
// 定义第二个指针 P2
ListNode 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 个节点。这种方法不仅简单明了,而且在大多数情况下都能提供良好的性能表现。在处理链表相关问题时,双指针技术是一个非常有用的工具。希望本文的讲解能帮助你更好地理解和解决类似的链表问题。
- 点赞
- 收藏
- 关注作者
评论(0)