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、具体代码剖析

1. class Solution {
2. public:
3.     int kthToLast(ListNode* head, int k) {
4.         // 初始化两个指针，分别指向链表的头节点
5.         ListNode* fast = head;
6.         ListNode* slow = head;
8.         // 让 fast 指针先走 k 步
9.         while (k--) {
10.             fast = fast->next;
11.         }
13.         // 同时移动 fast 和 slow，直到 fast 到达链表的末尾
14.         // 当 fast 到达链表末尾时，slow 则正好指向倒数第 k 个节点，返回该节点的值
15.         while (fast) {
16.             fast = fast->next;
17.             slow = slow->next;
18.         }
20.         // slow 现在指向倒数第 k 个节点，返回该节点的值
21.         return slow->val;
22.     }
23. };

复制代码

4、时间复杂度与空间复杂度

• 时间复杂度：O(n)，此中 n 为链表的长度。由于我们只遍历了链表一次，因此时间复杂度是线性的。
  
• 空间复杂度：O(1)，只用了两个指针，空间开销很小。
  

通过利用双指针本事，我们可以在一次遍历中高效地找到倒数第 k 个节点。这个解法在不需要额外空间的情况下，可以或许很好地解决问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告