每日leetcode——JZ22 链表中倒数最后k个结点数据结构与算法

题目输入一个长度为 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)了。
【每日leetcode——JZ22 链表中倒数最后k个结点】进阶思路：如何不翻转链表，只需要正序遍历链表节点，就能够找到倒数第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 Nonefor i in range(k-1): if former.next: former=former.next else: return Nonewhile former.next: pHead = pHead.next former = former.next return pHead