來源于「Krahets」的《圖解算法數據結構》
https://leetcode.cn/leetbook/detail/illustration-of-algorithm/

題目描述

訓練計劃 II

給定一個頭節點為 head 的鏈表用于記錄一系列核心肌群訓練項目編號，請查找并返回倒數第 cnt 個訓練項目編號。

示例 1：

輸入：head = [2,4,7,8], cnt = 1 輸出：8

提示：

1 <= head.length <= 100 0 <= head[i] <= 100 1 <= cnt <= head.length

思路

1. 兩種解法：快慢指針 / 遞歸（類似與鏈表反轉）

遞歸解法

1. 遞歸終止條件：遍歷到最后一個節點
2. 遞歸傳參：本輪節點的下一個節點 cur、計數值指針 pcnt
3. 遞歸開始返回后的操作：遞減計數值
4. 遞歸返回值：如果還未遞減計數值時，計數值已經歸零，則表面前面已經找到了正確的結果，直接返回這個結果即可；如果還未遞減計數值時，計數值不為0，則還未找到正確結果，應該遞減計數值并判斷，本輪找到了就返回即可，沒找到就返回空

/*** 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* recuList(ListNode* cur, int* pcnt){if(!cur) return nullptr;//遞歸終止條件：遍歷到最后一個節點ListNode* res = recuList(cur->next, pcnt);//進行遞歸傳參//如果計數還沒減就為0了，說明前面已經找到了正確的結果，直接使用正確的函數返回值返回if(*pcnt == 0) return res;//否則就是還沒找到正確結果，遞減計數器并判斷本輪節點是否就是要找的節點--(*pcnt);if(*pcnt == 0) return cur;//本輪未找到正確的元素，返回空return nullptr;}ListNode* trainingPlan(ListNode* head, int cnt) {return recuList(head, &cnt);}
};

快慢指針

• 這個方法基于一個樸素的思想，就是讓兩個指針相距 cnt，然后同時移動這兩個指針，直到快指針 fast 遍歷到鏈表尾，此時由于兩個指針相距 cnt，慢指針 low 就指向要尋找的節點

/*** 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* fast = head;ListNode* low = head;for(int i=cnt; i>0; --i){fast = fast->next;}while(fast){fast = fast->next;low = low->next;}return low;}
};