[LeetBook]【学习日记】类链表反转——寻找倒数第cnt个元素

来源于「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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

快慢指针

• 这个方法基于一个朴素的思想，就是让两个指针相距 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26