链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路

利用双指针，一个指针先走k-1步，然后两个指针同时开始走。第一个指针到尾部的时候，第二个指针指向倒数第k个结点。

代码

class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        count_k = 0
        p1 = head
        p2 = head
        while k > 1:
            if p1.next != None:
                p1 = p1.next
                k = k - 1
            else:
                return None
        while p1.next != None:
            p1 = p1.next
            p2 = p2.next
        return p2