快慢指针

找出单向链表中倒数第 k 个节点。返回该节点的值
普通解法时间复杂度2N

def kthToLast(self, head: ListNode, k: int) -> int:
        node = head
        length = 1
        while node.next:
            node = node.next
            length+=1
        node = head
        for _ in range(length-k):
            node = node.next
        return node.val

用快慢指针只用循环一遍N就行了

def kthToLast(self, head: ListNode, k: int) -> int:
        a=head
        b=head
        for i in range(k):
            b=b.next
        while b:
            a=a.next
            b=b.next
        return a.val