本文共 1650 字，大约阅读时间需要 5 分钟。

本系列文章为《剑指Offer》刷题笔记。

刷题平台：

思路1 自然而然想到使用容器（列表、堆栈、数组等）保存链表，然后直接查询

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def FindKthToTail(self, head, k):        # write code here        if not head or k<1:            return None            # 使用列表保存链表结构        stack = []        cur = head        while cur:            stack.append(cur)            cur = cur.next            # 非法情况，即K大于链表长度        if k > len(stack):            return None            return stack[-k]

思路2 （更快）

使用两个指针，同时都指向头结点，首先第一个指针走k-1步，即第一个结点到达第k个结点；然后两个指针同时往后移动，直到第一个指针到达链表末尾时停止，这时候第二个指针的指向是倒数第k个结点，最后返回第二个指针指向的节点

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def FindKthToTail(self, head, k):        # write code here        if not head or k<1:            return None        p1 = head        p2 = head        # 首先将p1移动k-1步，到达第k个节点        for _ in range(k-1):            p1 = p1.next            if p1 == None:    # 判断k的值是否大于链表长度，如果大于的话，p1会指向None                return None        # 当p1走到链表最后一个节点的时候，p2位于倒数第k个位置        while p1.next:            p1 = p1.next            p2 = p2.next        return p2

正常的思考过程：

（1）找到链表结尾，往回查找k个节点。写程序时逆向查找可能不好理解。 （2）用一个指针先走，另一个指针跟前一个指针保持k-1的差距，当第一个指针到达链尾，第二个指针就停在倒数第k个了

参考

https://blog.csdn.net/qq_18254385/article/details/94454415?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.not_use_machine_learn_pai&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.not_use_machine_learn_pai

.

https://cuijiahua.com/blog/2017/12/basis_14.html