剑指Offer第14题-链表中倒数第k个节点

题目

输入一个链表，输出该链表中倒数第k个结点。

考察点

代码稳健性

思路

其中一个比较普遍的思路是用两个指针p,q指向链表头部，p比q先跳k-1步，
然后p,q再一起移动，这样当p到达链表尾部的时候，q刚好就指向倒数第k的节点。

优点：

• 相当于构造了一把长度为k的尺子，没有用其他数据结构。
• 只需遍历一遍链表，时空复杂度都为O(n)

因为这题的考察点在于稳健性，所以要尽可能考虑到测试用例中可能出现的情况，比如 k >= 链表长度 的情况。

e.g.输入 {1,2,3,4,5} 
当k = 5，应返回{1,2,3,4,5}
当k > 5， 应返回{}

代码

代码翻译自牛客网某大牛的java代码

# -*- 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
        p = head
        q = head
        i = 0
        while p:
            if i >= k:
                q = q.next
            p = p.next
            i += 1
        return None if i < k else q