22链表中倒数第k个结点

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

class ListNode(object):
    def __init__(self, val, nxt=None):
        self.value = val
        self.next = nxt


def find_kth_to_tail(head, k):
    """
    @author: 黄健楸
    @aim:    输入一个链表，输出该链表中倒数第k个结点。
    @param:  head 头节点
    @param:  k    倒数第k个
    两个指针，一个指针先走k-1步，走到第K个节点，后两个节点一起走，
    当先走的指针走到链表尾部时，后走的指针便倒数第k个结点
    """
    if head is None or k == 0:
        return None
    probe_prev = head
    for _ in range(k - 1):
        if probe_prev.next:
            probe_prev = probe_prev.next
        else:
            return None
    probe_back = head
    while probe_prev.next:
        probe_prev = probe_prev.next
        probe_back = probe_back.next
    return probe_back


if __name__ == "__main__":
    d = ListNode('d')
    c = ListNode('c', d)
    b = ListNode('b', c)
    a = ListNode('a', b)
    # print(find_kth_to_tail(a, 2))
    assert find_kth_to_tail(a, 4) is a
    assert find_kth_to_tail(a, 2) is c
    assert find_kth_to_tail(a, 1) is d
    assert find_kth_to_tail(a, 5) is None
    # void = ListNode(None)
    assert find_kth_to_tail(None, 2) is None
    assert find_kth_to_tail(a, 0) is None