02.02、返回倒数第 k 个节点

02.02、[简单] 返回倒数第 k 个节点1、题目描述实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。2、题解思路本题的关键在于使用双指针法通过两个指针fast和slow让fast指针比slow指针先走k步这样当fast到达链表末尾时slow正好指向倒数第k个节点。具体步骤如下初始化两个指针fast和slow都指向链表的头节点。让fast先走k步使得fast和slow之间的距离为k。同时移动fast和slow直到fast到达链表的末尾。此时slow指针所指向的节点就是倒数第k个节点返回该节点的值。3、详细代码解析class Solution { public: int kthToLast(ListNode* head, int k) { // 初始化两个指针分别指向链表的头节点 ListNode* fast head; ListNode* slow head; // 让 fast 指针先走 k 步 while (k--) { fast fast-next; } // 同时移动 fast 和 slow直到 fast 到达链表的末尾 // 当 fast 到达链表末尾时slow 则正好指向倒数第 k 个节点返回该节点的值 while (fast) { fast fast-next; slow slow-next; } // slow 现在指向倒数第 k 个节点返回该节点的值 return slow-val; } };4、时间复杂度与空间复杂度时间复杂度O(n)其中n为链表的长度。由于我们只遍历了链表一次因此时间复杂度是线性的。空间复杂度O(1)只用了两个指针空间开销很小。通过使用双指针技巧我们可以在一次遍历中高效地找到倒数第k个节点。这个解法在不需要额外空间的情况下能够很好地解决问题。