方法一

利用数组，先遍历，再创建新链表。

• 时间复杂度和空间复杂度都为O（N）。

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        a = []
        while pHead:
            a.append(pHead.val)
            pHead = pHead.next

        if len(a) < k:
            return None # 注意这个！！！空链表
        
        newL = ListNode(-1)
        res = newL
        for i in a[len(a)-k:]:
            newL.next = ListNode(i)
            newL = newL.next
        
        newL.next = None
        return res.next

方法二

先获取链表长度length，再遍历length-k个节点，最后指向当前节点即可。

• 时间复杂度为O（N）;
• 空间复杂度为O（1）。

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        length = 0
        p = pHead

        while p:
            length += 1
            p = p.next
        
        if length < k:
            return None
        
        p = pHead
        for i in range(length-k):
            p = p.next
        
        return p

方法三

利用双指针，快指针先走k步，然后慢指针和快指针同时走，最后返回慢指针即可。

• 时间复杂度为O（N）;
• 空间复杂度为O（1）。

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        slow = pHead
        fast = pHead

        for i in range(k):
            if fast != None:
                fast = fast.next
            else:
                return None

        while fast:
            fast = fast.next
            slow = slow.next
        
        return slow