题目描述:
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
示例1
输入:{1,2,3,4,5},2
返回值:{4,5}
说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。
思路:
设置两个指针指向头结点。然后快指针往前移动k-1步(这是为了两个指针之间相差k)。最后快慢指针同时前进,当快指针到达末尾时,慢指针正好指向倒数k结点上。
python代码实现
class Solution:
def FindKthToTail(self , pHead , k ):
# write code here
fast=pHead
slow=pHead
for i in range(0,k):
if not fast:
return None
fast=fast.next
while fast:
fast=fast.next
slow=slow.next
return slow