力扣对应题目链接：LCR 140. 训练计划 II - 力扣（LeetCode）
核心考点 ：链表，前后指针的使用，边界条件检测。
一、《剑指Offer》内容
二、分析问题
较优解题思路：
- 题目中的链表是单链表，也就不能从后往前进行。
- 可以定义两个指针（快慢双指针），fast 指针先走 k 步，再让 slow 指针跟在后面，使用 “前后指针” 的方式，当 fast 指针到达结尾，slow 指针也就是倒数第 k 个节点。（其实原理就是：fast 指针和 slow 指针之间一直保持着 k 的距离）
三、代码
//力扣AC代码 /** * 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* slow=head; while(cnt>0 && fast!=nullptr) { fast=fast->next; cnt--; } while(fast!=nullptr) { fast=fast->next; slow=slow->next; } return slow; } }; //严谨写法 /** * 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) { if(head==nullptr || cnt<0) return head; ListNode* fast=head; ListNode* slow=head; while(cnt>0 && fast!=nullptr) { fast=fast->next; cnt--; } while(fast!=nullptr) { fast=fast->next; slow=slow->next; } if(cnt>0) return nullptr; else return slow; } };
四、扩展
力扣对应题目链接：876. 链表的中间结点 - 力扣（LeetCode）
1、分析题目
- 如果链表中结点总数为奇数，返回中间结点。
- 如果结点总数是偶数，返回中间两个结点的任意一个。
为了解决这个问题，我们也可以向上面那道题一样定义一个 fast 和 slow 指针，同时从链表的头结点出发，slow 指针一次走一步，fast 指针一次走两步。当 fast 指针走到链表的末尾时，slow 指针正好在链表的中间。
2、代码
//力扣AC代码 /** * 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* middleNode(ListNode* head) { ListNode* slow=head; ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; } return slow; } };
力扣对应题目链接：141. 环形链表 - 力扣（LeetCode）
1、分析题目
这道题也一样，定义两个指针 fast 和 slow，同时从链表的头结点出发，slow 指针一次走一步，fast 指针一次走两步。
- 如果 fast 指针追上了 slow 指针，那么链表就是环形链表。
- 如果 fast 的指针走到了链表的末尾（m_pNext 指向 NULL）都没有追上 slow 指针，那么链表就不是环形链表。
2、代码
（1）写法一（推荐）
//力扣AC代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow=head; ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) return true; } return false; } };
（2）写法二
//力扣AC代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(head==NULL || head->next==NULL) return false; ListNode* slow=head; ListNode* fast=head->next; while(fast!=slow) { if(fast==NULL || fast->next==NULL) return false; slow=slow->next; fast=fast->next->next; } return true; } };
五、举一反三
当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针（快慢双指针）来遍历链表。可以让 fast 指针遍历快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。
