【手撕OJ题】——BM8 链表中倒数最后k个结点

2024-08-23 06:04

文章标签 链表 oj 结点倒数 bm8

本文主要是介绍【手撕OJ题】——BM8 链表中倒数最后k个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🕒 题目

🔎 BM8 链表中倒数最后k个结点【难度：简单🟢】

输入一个长度为 n 的链表，设链表中的元素的值为 $a_i$ ，返回该链表中倒数第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
输出：{}
解释：返回一个长度为 0 的链表。

⌛ 方法① - 直接遍历

💡 思路：遍历整个链表以计算出链表的长度n，然后倒数第k个元素即为第n-k个正数元素。
注意：在以下情况下应直接返回NULL：

链表为空或k<=0
k的值超过了链表的长度

代码实现如下：

struct ListNode* FindKthToTail(struct ListNode* pHead, int k) {// 判断链表非空if (pHead == NULL || k <= 0) {return NULL;}// 定义一个计数器用来计算链表长度int count = 0;// 遍历链表struct ListNode* cur = pHead;while (cur) {cur = cur->next;  // cur指针右移count++;  // 计数器 +1}// 判断 k 是否大于链表长度if (count < k) {return NULL;}// 新的头节点struct ListNode* NewHead = pHead;for (int i = 0; i < count - k; i++) {NewHead = NewHead->next;}return NewHead;
}

⌛ 方法② - 快慢指针

💡 思路：一次遍历即可找到中间节点。定义两个指针 fast 和 slow，先让 fast 走k或k-1步，然后让 fast 和 slow 一起走：

fast 先走k步时，当 fast == NULL，slow 为倒数第k个元素；
fast 先走k-1步时，当 fast->next == NULL，slow 为倒数第k个元素；这里与链表长度为奇数或者偶数无关。

在这里插入图片描述

代码实现如下：

struct ListNode* FindKthToTail(struct ListNode* pHead, int k) {struct ListNode* fast;struct ListNode* slow;fast = slow = pHead;// 让fast先走K步while (k--) {if (fast == NULL) {return NULL;}fast = fast->next;}while (fast) {fast = fast->next;slow = slow->next;}return slow;
}