Problem: LCR 140. 训练计划 II

题目描述

思路

思路1：顺序遍历

欲返回倒数第cnt个节点则需要顺序遍历到len-cnt（其中len为链表的长度）

思路2：快慢指针

让一个快指针fast指向cnt + 1个节点，慢指针slow指向头节点，再同时后移动，当快指针为空时，则慢指针指向的为倒数cnt号节点

复杂度

思路1:
时间复杂度:

$O(n)$;其中$n$为链表的长度

空间复杂度:

$O(1)$

思路2:
时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

思路1：

class Solution {
public:/*** Sequential search** @param head The head node of linked list* @param cnt Given number* @return ListNode**/ListNode* trainingPlan(ListNode* head, int cnt) {int len = 0;ListNode* p = head;while (p != nullptr) {p = p -> next;len++;}p = head;for (int i = 0; i < len - cnt; ++i) {p = p -> next;}return p;}
};

思路2：

/*** 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:/***Fast and slow pointer** @param head The head node of linked list* @param cnt Given number* @return ListNode**/ListNode* trainingPlan(ListNode* head, int cnt) {ListNode* fast = head;ListNode* slow = head;for (int i = 0; i < cnt; ++i) {fast = fast -> next;}while (fast != nullptr) {fast = fast -> next;slow = slow -> next;}return slow;}
};