链表中倒数第 k 个节点（ 剑指Offer 22 ）
一、题目描述
输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6 。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
二、题目解析
一般来说，链表相关的算法题考察的知识点有以下几个：
- 递归
- 反转
- 双指针
- 环
本题解题思路如下：
- 1、初始化两个指针
former和latter，一开始都指向链表的头节点 - 2、前指针
former先向前走 k 步 - 3、两个指针
former和latter同时向前移动，直到前指针former指向NULL - 4、由于 former 和 latter 之间的距离为 k，所以 latter 指向的节点即是倒数第 k 个节点，最后返回
latter
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 链表中倒数第 k 个节点（ 剑指Offer 22 ）:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
//初始化两个指针 former 和 latter，一开始都指向链表的头节点
// 指针 former 指向链表的头节点
ListNode former = head;
// 指针 latter 指向链表的头节点
ListNode latter = head;
// 让 former 指针先向前走 k 步
for (int i = 0 ; i < k; i++){
// former 指针向后移动
former = former.next;
}
// 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
while(former != null){
// former 指针向后移动
former = former.next;
// latter 指针向后移动
latter = latter.next;
}
// 此时，由于 former 和 latter 之间的距离为 k
// 所以 latter 指向的节点即是倒数第 k 个节点
return latter;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 链表中倒数第 k 个节点（ 剑指Offer 22 ）:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//初始化两个指针 former 和 latter，一开始都指向链表的头节点
// 指针 former 指向链表的头节点
ListNode* former = head;
// 指针 latter 指向链表的头节点
ListNode* latter = head;
// 让 former 指针先向前走 k 步
for (int i = 0 ; i < k; i++){
// former 指针向后移动
former = former->next;
}
// 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
while(former != NULL){
// former 指针向后移动
former = former->next;
// latter 指针向后移动
latter = latter->next;
}
// 此时，由于 former 和 latter 之间的距离为 k
// 所以 latter 指向的节点即是倒数第 k 个节点
return latter;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 链表中倒数第 k 个节点（ 剑指Offer 22 ）:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
# 初始化两个指针 former 和 latter，一开始都指向链表的头节点
# 指针 former 指向链表的头节点
former = head
# 指针 latter 指向链表的头节点
latter = head
# 让 former 指针先向前走 k 步
for i in range(k) :
# former 指针向后移动
former = former.next
# 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 None
while former != None :
# former 指针向后移动
former = former.next
# latter 指针向后移动
latter = latter.next
# 此时，由于 former 和 latter 之间的距离为 k
# 所以 latter 指向的节点即是倒数第 k 个节点
return latter
