题目

输出一个长度为 n 的链表，设链表中的元素的值为 ai，返回该链表中倒数第 k 个节点。
如果该链表长度小于 k，请返回一个长度为 0 的链表。

要求：空间复杂度 O(n)，工夫复杂度 O(n)
进阶：空间复杂度 O(1)，工夫复杂度 O(n)

示例 1
输出：{1,2,3,4,5},2
返回值：{4,5}
阐明：返回倒数第 2 个节点 4，零碎会打印前面所有的节点来比拟。示例 2
输出：{2},8
返回值：{}

思路

最间接的思路是：翻转整个链表，而后再遍历节点，这样做就是空间复杂度 O(n)，工夫复杂度 O(n)
空间复杂度 O(1)，则不能存储额定的链表，意味着只能在原链表上操作。
如果先遍历一遍链表，失去链表的长度，再减去 k，失去倒数第 k 个节点是正序第几个节点，这样的做法工夫复杂度又不满足 O(n)了。

进阶思路：如何不翻转链表，只须要正序遍历链表节点，就可能找到倒数第 k 个节点呢
尾节点作为倒数第 1 个节点，从它往前挪动 k - 1 个节点，就是倒数第 k 个节点。
所以倒数第 k 个节点，和尾节点之间的间隔，是 k - 1 步。
咱们设置两个指针，former 和 latter，latter 在头节点处，former 比 latter 往前 k - 1 步，而后同时挪动两个指针，直到 former 指向了尾节点，此时 latter 指向的节点就是倒数第 k 个节点了，这样通过正序遍历节点，就能找到倒数第 k 个节点了。

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
    former = pHead
    if not former or not former.next or k==0:
        return None
    
    for i in range(k-1):
        if former.next:
            former=former.next
        else:
            return None
        
    while former.next:
        pHead = pHead.next
        former = former.next
    return pHead