力扣面试题02.02：返回倒数第k个节点 - 快慢指针解法详解

内容简介

本文详细解析了力扣面试题02.02"返回倒数第k个节点"的高效解法。通过快慢指针技巧，展示了如何在不预先知道链表长度的情况下，仅用一次遍历就找到目标节点。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握链表操作的核心技巧。

算法思路

‌快慢指针初始化‌：两个指针都从链表头开始

‌快指针先行‌：快指针先向前移动k步

‌同步移动‌：然后快慢指针同时移动直到快指针到达末尾

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

代码实现（带详细注释）

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        // 初始化快慢指针，都指向链表头
        ListNode* fast = head;
        ListNode* slow = head;
        
        // 快指针先向前移动k步
        for(int i = 0; i < k; i++) {
            fast = fast->next;
        }
        
        // 快慢指针同步移动，直到快指针到达链表末尾
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 返回慢指针当前指向的节点值(倒数第k个节点)
        return slow->val;
    }
};

复杂度分析

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

‌空间复杂度‌：O(1)，仅使用固定数量的指针变量

优化方向

‌错误处理‌：添加对k值大于链表长度的检查

‌边界条件‌：处理空链表或k=0的情况

‌递归实现‌：展示另一种递归解法作为对比

总结

快慢指针法是解决链表定位问题的经典技巧，该解法高效且直观，是面试中的常见考点。掌握这种双指针技巧对解决各类链表问题大有裨益。