力扣LCR140题：训练计划II - 链表中倒数第k个节点解法详解

内容简介

本文详细解析了力扣LCR140题"训练计划II"的链表操作解法，该题实际上是剑指Offer22题的变体，要求找出链表中倒数第k个节点。通过快慢指针技巧，只需一次遍历即可高效解决问题，时间复杂度为O(n)。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握链表操作的核心技巧。

算法思路

‌双指针初始化‌：快指针(fast)和慢指针(slow)都指向链表头节点

‌快指针先行‌：快指针先向前移动k个节点，构建两指针间的固定距离

‌同步移动‌：两指针同时移动，直到快指针到达链表末尾

‌慢指针定位‌：此时慢指针指向的就是倒数第k个节点

代码实现（带详细注释）

class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* fast = head;  // 快指针，用于先行探测
        ListNode* slow = head;  // 慢指针，最终指向目标节点
        
        // 快指针先移动cnt步，建立两指针间的距离
        while(cnt-- && fast) {  // 添加fast判空防止k大于链表长度
            fast = fast->next;
        }
        
        // 两指针同步移动，直到快指针到达链表末尾
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;  // 返回倒数第k个节点
    }
};

复杂度分析

‌时间复杂度‌：O(n)，只需遍历链表一次

‌空间复杂度‌：O(1)，仅使用常数空间

边界条件处理建议

‌空链表处理‌：添加头节点判空逻辑

‌k值过大处理‌：当k大于链表长度时返回nullptr

‌k值非法处理‌：添加对k≤0的情况处理

总结

快慢指针法是解决链表倒数第k个节点问题的高效方案，通过巧妙的两指针间距控制，避免了多次遍历链表，是面试中常见的考察点。理解这种解法有助于掌握链表操作和双指针技巧的核心思想