问题：实现一个函数，输入k，返回给定链表中的倒数第k个结点。

原理：

不难看出，链表的倒数第k个结点就是链表的第(n-k+1)个结点（前提是k<=n）。第(n-k+1)个结点可以表示如下：

n-k+1 = n-(k-1)

因此，就可以把倒数第k个结点和尾结点的举例(k-1)，如果你觉得不够直观可以画图理解。这样，我们在遍历链表时可以使用一_sentinel哨兵指针和正常指针pointer，保持它们的距离为k-1。哨兵指针_sentinel指向最后一个结点的时候，正常指针pointer就指第n-k+1个结点，也就是倒数第k个结点。

那么怎样保持pointer指针和_sentinel距离为恒定值k呢？这个容易：在一开始时先让_sentinel走k-1步。

这就是解决该问题的大概思路，但需要注意一下细节：k所指定的结点要在链表范围内，否则会出现越界，指定的结点根本不在链表内。具体表现在，_sentinel移动没有达到k-1步就已经到达链表结尾。

实现步骤：
（1）对异常输入的检测
（2）_sentinel指针位移k-1步，如果在到达k-1结点前到达链表结尾，则出错
（2）同时移动pointer和_sentinel直到后者到达链表结尾。
（4）_sentinel到达链表结尾后，如果

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def last_k_node(p_head, k):
    if not p_head:
        raise ValueError("p_head is None")
    if k <= 0:
        raise ValueError("k must be positive")
    p1 = p_head
    p2 = p_head

    n = 0
    for _ in range(k):
        p1 = p1.next
        n += 1
        if p1 is None and n != k-1:
            raise ValueError("p_head's length < k")
    while p1:
        p1 = p1.next
        p2 = p2.next
        n += 1
        if p1 is None:
            break
    return p2

测试代码

1
2
3
4
5
6
7
def main():
    p_head = build_linked_list(range(10))
    node_9 = last_k_node(p_head, 1)
    print("last 1 node", node_9)

    node_6 = last_k_node(p_head, 4)
    print("last 4 node", node_6)

测试结果如下

1
2
3
>>> main()
last 1 node Node<9>
last 4 node Node<6>

完。