LCK 140.训练计划2 返回链表倒数第K个节点
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
示例 1：
输入：head = [2,4,7,8], cnt = 1 输出：8
思路详解：本题我们使用两种办法解决，第一种我们先顺序遍历一次链表，记录链表的节点总数，然后再次循环节点总数减去目标位数就是我们要的倒数第k个节点
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
int index=0;
ListNode*node=head;//记录头节点并循环然后记录整个链表的总结点数
while(node)
{
index++;
node=node->next;
}
for(node=head;index>cnt;index--)//再次循环找到所需节点即可
{
node=node->next;
}
return node;
}
};当然我们还可以用双指针的办法来解决，定义两个指针，一个指针快一个指针慢，让快指针先走cnt个节点，然后让快慢指针一起走直到快指针走到null此时慢指针指向的节点就是我们的倒数第K个节点，如果不理解可以看下面的图，p1为快指针第一次停下的位置，q1为快指针走到NULL时所指位置
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode*fast=head;//定义快慢指针，让他们都指向头节点
ListNode*slow=head;
for(int i=0;i<cnt;i++)
{
fast=fast->next;//先让快指针走。走过cnt个节点数
}
while(fast)
{
fast=fast->next;//如果fast没有走到NULL就让两个指针一起走
slow=slow->next;//快指针停下后，慢指针所指向的节点就是倒数第n个节点
}
return slow;
}
};面经：
1. new或malloc在申请空间时，超出可申请的大小就会分配异常，可申请的大小是多少
没有一个固定的“可申请的大小”，因为这取决于上述所有因素。举个例子，如果你在一个具有4GB物理内存的32位系统上，理论上你的程序可能无法使用超过4GB的内存，但实际上，由于操作系统和其他程序也需要内存，单个程序可能只能分配到几百兆到几字节。
2. C++循环引用指的是什么，在使用过程当中需要注意什么问题
在C++中，循环引用指的是两个或多个对象相互持有对方的引用（或指针），形成一个闭环，这样就会导致引用计数无法正确地归零，从而无法释放这些对象占用的内存。循环引用通常出现在使用引用计数（如智能指针shared_ptr）来管理动态分配的对象时。比如下面这段例子
#include <memory>
using namespace std;
class ClassA {
public:
shared_ptr<ClassB> ptrB;
~ClassA() { cout << "ClassA destroyed" << endl; }
};
class ClassB {
public:
shared_ptr<ClassA> ptrA;
~ClassB() {cout << "ClassB destroyed" << endl; }
};
int main() {
{
auto a = make_shared<ClassA>();
auto b = make_shared<ClassB>();
a->ptrB = b;
b->ptrA = a;
} // 当离开这个作用域时，我们期望a和b被销毁，但由于循环引用，它们不会
return 0;
}
如何避免循环引用：
- 避免循环引用：在设计类和对象关系时，应尽量避免形成循环引用。
- 使用弱引用：如果循环引用不可避免，可以使用weak_ptr来打破循环。weak_ptr是一种不增加引用计数的智能指针，它指向由shared_ptr管理的对象。
- 手动打破循环：在某些情况下，可以在适当的时机手动断开循环引用，比如在某个对象的生命周期结束时。