剑指offer 链表中倒数最后k个结点

题目描述:
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。

示例1
输入:{1,2,3,4,5},2
返回值:{4,5}
说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。

思路:
设置两个指针指向头结点。然后快指针往前移动k-1步(这是为了两个指针之间相差k)。最后快慢指针同时前进,当快指针到达末尾时,慢指针正好指向倒数k结点上。
python代码实现

class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        fast=pHead
        slow=pHead
        for i in range(0,k):
            if not fast:
                return None
            fast=fast.next
        while fast:
            fast=fast.next
            slow=slow.next
        return slow
上一篇:数据结构//C——动态分配—离散存储(非循环单链表)2


下一篇:【数据结构-C】双向循环链表基本操作及图解分析