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

ftggdnt

内容简介

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

算法思路

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

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

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

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

代码实现（带详细注释）

1. class Solution {
   
2. public:
   
3.     ListNode* trainingPlan(ListNode* head, int cnt) {
   
4.         ListNode* fast = head;  // 快指针，用于先行探测
   
5.         ListNode* slow = head;  // 慢指针，最终指向目标节点
   
6.         
   
7.         // 快指针先移动cnt步，建立两指针间的距离
   
8.         while(cnt-- && fast) {  // 添加fast判空防止k大于链表长度
   
9.             fast = fast->next;
   
10.         }
    
11.         
    
12.         // 两指针同步移动，直到快指针到达链表末尾
    
13.         while(fast) {
    
14.             fast = fast->next;
    
15.             slow = slow->next;
    
16.         }
    
17.         
    
18.         return slow;  // 返回倒数第k个节点
    
19.     }
    
20. };

复制代码

复杂度分析

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

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

边界条件处理建议

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

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

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

总结

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

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