难度: Easy
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2 输出： 4
说明：
给定的 k 保证是有效的。
Submission
运行时间: 44 ms
内存: 14.9 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
f = s = head
for _ in range(k):
f = f.next
while f:
f = f.next
s = s.next
return s.val
Explain
此题解采用了双指针方法（快慢指针）。首先，两个指针 f（快指针）和 s（慢指针）都指向链表的头节点 head。然后，快指针 f 先向前移动 k 步。这样，快慢指针之间就保持了 k 个节点的间隔。接着，快慢指针同时向前移动，直到快指针 f 指向链表的末尾（即 f 为 None）。此时，慢指针 s 指向的就是链表中的倒数第 k 个节点。返回该节点的值即可。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
# 初始化两个指针都指向头节点
f = s = head
# 移动快指针 f，使其领先慢指针 s k 步
for _ in range(k):
f = f.next
# 同时移动快慢指针，直到快指针到达链表末尾
while f:
f = f.next
s = s.next
# 此时慢指针指向倒数第 k 个节点
return s.val
Explore
在双指针方法中，快指针先移动k步的目的是在快指针和慢指针之间创建一个长度为k的间隔。当快指针从头节点开始移动k步后，如果快指针没有到达链表尾部，那么从快指针到链表末尾的距离加上这个k步的距离等于整个链表的长度。此时，如果继续移动快指针和慢指针，每当快指针向前移动一步，慢指针也向前移动一步，保持这个间隔不变。当快指针到达链表末尾节点的下一个位置（即None），慢指针刚好位于从链表末尾数起的第k个节点，因为从慢指针到链表末尾的距离加上k（慢指针到快指针的距离）等于链表总长度。
如果在移动快指针的过程中k步时快指针到达了链表的末尾，这通常意味着k大于或等于链表的长度。在这种情况下，程序应该进行额外的检查来处理这种情况，避免出现空指针异常。典型的处理方式是，首先在移动快指针之前检查k与链表长度的关系，如果k大于链表长度，可以返回一个错误信息或特殊值，或者根据实际需求可能需要返回链表的第一个节点（如果考虑倒数第k个节点是从1开始计数的话）。
这个逻辑关系基于快慢指针之间维持的固定距离k。当快指针先行移动k步之后，快慢指针之间的距离就固定为k。当快指针继续移动，慢指针也开始移动，但这个距离始终保持不变。因为快指针从链表头部移动到链表尾部的下一个位置（即None）需要的步数等于链表的长度n。此时慢指针也从头部向前移动了n-k步。因此，慢指针现在的位置就是从链表头部开始的第n-k+1个位置，这也正是整个链表的倒数第k个位置。