剑指offer-14、链表中倒数第k个结点
题⽬描述输⼊⼀个链表，输出该链表中倒数第k个结点。
例如输⼊{1,2,3,4,5} , 2 时，对应的链表结构如下图所示：
其中蓝⾊部分为该链表的最后2 个结点，所以返回倒数第2 个结点（也即结点值为4 的结点）即可，系统会打印后⾯所有的节点来⽐较。
示例1
输⼊：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后⾯所有的节点来⽐较。
示例2
输⼊：{2},8
返回值：{}
思路及解答
两次遍历法
[*]第一次遍历计算链表长度n
[*]第二次遍历到第n-K+1个节点（即倒数第K个节点）
[*]如果K大于链表长度，返回null
public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k <= 0) return null;
// 第一次遍历计算链表长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 检查k是否有效
if (k > length) return null;
// 第二次遍历找到目标节点
current = head;
for (int i = 0; i < length - k; i++) {
current = current.next;
}
return current;
}
[*]时间复杂度：O(n)，需要遍历链表两次
[*]空间复杂度：O(1)，只使用了固定数量的指针
双指针法（推荐）
快慢双指针，先让第1 个指针先⾛k 步，然后第2 个指针开始⾛，⽽且两个指针⼀起⾛，直到第⼀个指针⾛到最后的位置。
[*]使用快慢两个指针，快指针先移动K步
[*]然后两个指针同步移动，当快指针到达末尾时，慢指针正好指向倒数第K个节点
[*]如果快指针在移动K步前到达末尾，说明K大于链表长度
public ListNode findKthToTail(ListNode head, int k) { if (head == null || k
页:
[1]