title: 每日一练（12）：链表中倒数第 k 个节点
categories:[剑指 offer]
tags:[每日一练]
date: 2022/01/25
每日一练（12）：链表中倒数第 k 个节点
输出一个链表，输入该链表中倒数第 k 个节点。为了合乎大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值顺次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
办法一：程序查找
具体过程如下：
- 1、第一次遍历失去链表总长度 n。
- 2、第二次遍历到第 n−k+ 1 个节点，返回该节点所在的链表援用。
实现细节：
- 当 k > n 时，链表中没有该节点，咱们返回 nullptr。
- 工夫复杂度剖析：链表总共遍历两次，所以工夫复杂度是 O(n)
ListNode* getKthFromEnd(ListNode* head, int k) {
int n = 0;
for (ListNode *p = head; p; p = p->next) {// 失去链表总长度 n
n++;
}
if (k > n) { // 当 k > n 时，链表中没有该节点
return nullptr;
}
ListNode *node = head;
for (int i = 0; i < n-k; i++) {node = node->next; // 遍历到第 n−k+ 1 个节点，返回该节点所在的链表援用}
return node;
}办法二：快慢双指针
快慢指针的思维。咱们将第一个指针 fast 指向链表的第 k + 1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好距离 k 个节点。此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空节点时，则此时 slow 指针刚好指向链表的倒数第 k 个节点。
- 咱们首先将 fast 指向链表的头节点，而后向后走 k 步，则此时 fast 指针刚好指向链表的第 k+1 个节点。
- 咱们首先将 slow 指向链表的头节点，同时 slow 与 fast 同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *fast = head;
ListNode *slow = head; // 指针 slow 指向链表的第一个节点
while (fast && k > 0) {
fast = fast->next; // 指针 fast 指向链表的第 k + 1 个节点
k--;
}
while (fast) { // 两个指针同步向后走 当第一个指针 fast 走到链表的尾部空节点时
fast = fast->next;
slow = slow->next; // 此时 slow 指针刚好指向链表的倒数第 k 个节点
}
return slow; // 返回此时 slow 指向倒数的第 k 个节点
}