題目描述

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

思路

利用雙指針，一個(gè)指針先走k-1步，然后兩個(gè)指針同時(shí)開(kāi)始走。第一個(gè)指針到尾部的時(shí)候，第二個(gè)指針指向倒數(shù)第k個(gè)結(jié)點(diǎn)。

代碼

class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        count_k = 0
        p1 = head
        p2 = head
        while k > 1:
            if p1.next != None:
                p1 = p1.next
                k = k - 1
            else:
                return None
        while p1.next != None:
            p1 = p1.next
            p2 = p2.next
        return p2