【leetcode天梯】链表 · 022 链表中倒数第k个节点
时间：2022-11-25 17:30:00
题目描述：
输入链表，输出链表中倒数第K节点。为了满足大多数人的习惯，这个问题从1开始计数，即链表的尾节点是倒数第一节点。
示例 1：
例如，链表有 从头节点开始，五个节点的值依次是 1、2、3、4、5。链表倒数第二 两个节点值为 4 的节点。
输入：head = [1，2，3，4，5] , k=2 输出：[4，5]示例 2：
输入：head = [1，2，3，4，5] , k=100 输出：[]示例 3：
输入：head = [] , k=1 输出：[]题目链接：
剑指 Offer 22. 倒数第中倒数第k节点 - 力扣（LeetCode）https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/倒数第k结点在链表中_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
这里牛客网的检验案例更多，推荐使用牛客暴刷！
解题思路：
常规法1:早晚指针
这是一种非常经典的做法，是指针快慢变形操作。我们设置了两个指针，其中指针late比指针early早走k步，然后让指针early与指针late共同向后遍历，当指针late指向NULL时，指针early指向结点恰好是倒数第k个结点。
struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode* late = head; struct ListNode* early = head; while(k--) { if(late!=NULL) //当late不为空时，late一直向后走 late=late->next; else return NULL;//当未满k步late就已经走到NULL直接返回NULL，不能得到倒数第的结点 } while(late) //late指针与early指针一直到late指针指向空时停止 { early=early->next; //early向后走一步 late=late->next; //late向后走一步 } return early; }总结一下：这是一个非常典型的快慢指针问题，我相信你可以记住这种方法，非常经典和易于使用！
