更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

链表中倒数最后k个节点

问题描述

LeetCode 剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

输入：{1,2,3,4,5}，2

输出：{4,5}

分析问题

这道题比较简单，我们可以直接使用快慢指针来求解，开始时申请两个指针同时指向链表的头结点，记为slow和fast，然后让fast先移动k步，再然后让两个指针slow和fast同时移动，使得fast和slow在移动的过程中总是相隔k个单位，当fast指针走到末尾的时候，此时slow正好指向的是倒数第k个位置。

image-20211031192747110

下面我们来看一下代码的实现。

class Solution:
    def FindKthToTail(self, pHead, k):
        #快慢指针同时执行头结点
        slow=fast=pHead
        #快指针移动k步
        for i in range(0,k):
            #如果还没走完k步就走到了链表尾，直接返回None
            if not fast:
                ‘return None
            fast = fast.next
        #两个指针同时移动,直到fast为空
        while fast:
            slow=slow.next
            fast=fast.next

        return slow