链表中倒数第k个节点

image.png

这个问题在作业帮面试的时候遇到了，哭哭:( ，都怪自己没有提前开始看书，再看半天就看到这里了，总是在浪费时间，哼╭(╯^╰)╮

首先最简单的方法是遍历一遍链表，算出n,然后遍历到第n-k个即可

面试官期待的是只需要一次遍历的算法：
要用两个指针，P1先走k-1步，到达第k个位置上，然后两个指针一起走，当P1走到尾部的时候，P2所指的位置就是倒数第k个位置

要注意的点：
当链表中节点个数不够k个：返回空
头指针为空
k为0

代码如下：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        p1 = head
        p2 = head
        for i in range(k):
            if p1 == None:
                return None
            p1 = p1.next
        while p1!=None:
            p1 = p1.next
            p2 = p2.next
        return p2

image.png