题解 | 链表中倒数最后k个结点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    """
    解题思路： 
    快慢指针
    """
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        cur=pHead
        n=0
        while cur:
            n+=1
            cur=cur.next
        if n<k:
            return None
        fast =pHead
        slow=pHead
        i=k
        while i>0:
            fast=fast.next
            i=i-1
        print("----")
        while fast:
            fast=fast.next
            slow=slow.next
        return slow

    """
    解题步骤： 
    1. 遍历一遍得到链表长度n
    2.比较 n与k ,如果比k小返回一个空节点
    3.移动n-k 次
    时间复杂度O(n) 总共遍历n 个链表元素
    空间复杂度O(1) 指针
    """
    def FindKthToTail1(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        #统计个数
        # 移动 n-k
        cur=pHead
        n=0
        while cur :
            cur=cur.next 
            n+=1
        if n<k:
            return None
        num =n-k-1
        newhead=pHead
        while num>0:
            num-=1
            newhead =newhead.next
        return newhead