Description

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

Solutions

当然第一印象就能想到两次遍历就能实现这个问题,第一遍能知道整个链表的大小 $n$,然后第二次遍历到 $n-k$ 个结点时输出即可。

但是这样暴力的方法一般很难令人满意,所以如果想只遍历一次链表要怎么办呢?

可以像判断链表上是否有环的那种方式,用两个指针,一个指针先走 k 步,然后能一个指针在和它同步走,当第一个指针走到头,第二个指针就指向倒数第 K 个结点。

class Solution:
    def FindKthToTail(self, head, k):
        if not head or k <= 0:
            return None
        first_p = head
        for i in range(k-1):
            if first_p.next is None:
                return None
            first_p = first_p.next
        second_p = head
        while first_p.next:
            second_p = second_p.next
            first_p = first_p.next
        
        return second_p

References

  1. 015. 链表中倒数第K个结点