剑指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
  

1. public ListNode findKthToTail(ListNode head, int k) {
2.     if (head == null || k <= 0) return null;
3.    
4.     // 第一次遍历计算链表长度
5.     int length = 0;
6.     ListNode current = head;
7.     while (current != null) {
8.         length++;
9.         current = current.next;
10.     }
11.    
12.     // 检查k是否有效
13.     if (k > length) return null;
14.    
15.     // 第二次遍历找到目标节点
16.     current = head;
17.     for (int i = 0; i < length - k; i++) {
18.         current = current.next;
19.     }
20.    
21.     return current;
22. }

复制代码

• 时间复杂度​：O(n)，需要遍历链表两次
  
• ​空间复杂度​：O(1)，只使用了固定数量的指针
  

双指针法（推荐）

快慢双指针，先让第1 个指针先⾛k 步，然后第2 个指针开始⾛，⽽且两个指针⼀起⾛，直到第⼀个指针⾛到最后的位置。

• 使用快慢两个指针，快指针先移动K步
  
• 然后两个指针同步移动，当快指针到达末尾时，慢指针正好指向倒数第K个节点
  
• 如果快指针在移动K步前到达末尾，说明K大于链表长度
  

[code]public ListNode findKthToTail(ListNode head, int k) {    if (head == null || k