02.02. 返回倒数第 k 个节点

1
2
3

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

1
2
3

反向思考，既然是寻找倒数第K个，那么计算机只能循环后移，不如我们先将位置确定，让其同步后移到链尾。
设置前后指针都先指向头结点，后指针先移动到第K个结点，那么前后指针此时相距K个位置。同步后移，当后指针指向链尾时，前指针就自然指向倒数第K个结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def kthToLast(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: int
        """
        if head is None:
            return None

        left = head
        right = head
        count = 0
        while count < k:
            right = right.next
            count += 1
        while right:
            left = left.next
            right = right.next
        return left.val