题目

实现一种算法，找出单向链表中倒数第k个节点。返回该节点的值。
image.png

思路

双指针。
快指针先走k步，然后快慢指针一起走，当快指针走到链表末端，慢指针所指向的位置就是倒数第k个节点。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def kthToLast(self, head: ListNode, k: int) -> int:
  9.         if head is None: return
  10.         slow, fast = head, head
  11.         for _ in range(k):
  12.             fast = fast.next
  13.         while fast is not None:
  14.             slow = slow.next
  15.             fast = fast.next
  16.         return slow.val