给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号,请查找并返回倒数第 cnt 个训练项目编号。
示例 1:
输入:head = [2,4,7,8], cnt = 1 输出:8
提示:
1 <= head.length <= 1000 <= head[i] <= 1001 <= cnt <= head.length
解题思路
双指针
国庆太摸鱼也不好,最近写了道双指针的题,不过那道比这道难,那道题还要删除节点。说实话删除节点我一直觉得很抽象,可能C++指针是这样的吧。
那就双指针呗,嗯….貌似没啥能讲的,有点简单了。看到相关题有个倒置链表的,用递归做下看看。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode*p1=head,*p2=head;
while(cnt!=0)
{
p2=p2->next;
cnt--;
}
while(p2!=NULL)
{
p2=p2->next;
p1=p1->next;
}
return p1;
}
};