【2024考研】题解7 | #链表中倒数最后k个结点#
链表中倒数最后k个结点
https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
/**（傻逼题）尾指针一直倒数着
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* FindKthToTail(ListNode* pHead, int k) {
// write code here
ListNode *tail = pHead;//尾指针
ListNode *ptail = pHead;//间断指针
int length = 0;
//测量链表长度
while(tail){
tail = tail->next;
length++;
}
//测试输出
// cout<<"长度："<<length<<endl;
//我没k，k大于链表长度的情况
if(k>length) return nullptr;
//时间（链表尾巴）一直倒数着
for(int i = 0; i < length-k; i++){
ptail = ptail->next;
}
return ptail;
}
};
/*
GPT总结的傻逼题：
时间复杂度：O(n)，其中n为链表的长度。算法遍历了一次链表来计算链表的长度，然后再遍历一次链表来找到倒数第k个节点，所以时间复杂度为O(n)。
空间复杂度：O(1)，算法只使用了常数个额外的指针变量来辅助遍历链表，没有使用额外的数据结构，所以空间复杂度为O(1)。
算法思想：首先遍历链表一次，计算链表的长度。然后再遍历链表一次，找到倒数第k个节点。为了找到倒数第k个节点，可以使用两个指针，一个先走k-1步，然后两个指针一起向后移动，直到第一个指针到达链表末尾，此时第二个指针指向的就是倒数第k个节点。
*/
2024考研数据结构 文章被收录于专栏
本人考研刷算法题，立此专栏练习强化。
查看20道真题和解析