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;
    }
};