1、題目描述
實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該節點的值。
注意：本題相對原題稍作改動
示例：
輸入： 1->2->3->4->5 和 k = 2
輸出： 4
說明：
給定的?k?保證是有效的。
2、方法1：兩次遍歷
-
第一次遍歷：計算鏈表的長度?
len。 -
第二次遍歷：從頭節點開始，移動?
len - k?步，到達倒數第?k?個節點。
關鍵步驟
-
計算鏈表長度：
-
初始化指針?
curr?指向頭節點?head，計數器?len = 0。 -
遍歷鏈表，每移動一次?
curr，len?加 1，直到?curr?為?null。 -
最終?
len?存儲的是鏈表的節點總數。
-
-
定位倒數第 k 個節點：
-
倒數第?
k?個節點就是正數第?len - k + 1?個節點。 -
由于鏈表從?
head?開始編號為?1，所以只需移動?len - k?步即可到達目標節點。 -
例如，鏈表?
1->2->3->4->5，k=2（倒數第 2 個節點是?4）：-
len = 5，len - k = 3。 -
從?
head?移動 3 步：1（初始）→?2?→?3?→?4，返回?4。
-
-
時間復雜度
-
O(n)，其中?
n?是鏈表的長度。-
第一次遍歷計算長度：
O(n)。 -
第二次遍歷定位節點：
O(n)。 -
總時間：
O(2n) = O(n)。
-
空間復雜度
-
O(1)，只使用了常數級別的額外空間（
curr?指針和?len?變量）。
public static ListNode kthToLast(ListNode head, int k) {ListNode curr = head;int len = 0;// 第一次遍歷：計算鏈表長度 lenwhile (curr != null) {len++;curr = curr.next;}// 第二次遍歷：移動 len - k 步for (int i = 0; i < len - k; i++) {head = head.next;}return head; // 返回倒數第 k 個節點
}3、方法2：快慢指針
使用快慢指針（Fast-Slow Pointer）來找到鏈表的倒數第?k?個節點：
-
初始化快慢指針：
fast?和?slow?都指向頭節點?head。 -
快指針先移動?
k-1?步：-
目的是讓?
fast?和?slow?之間相隔?k-1?個節點。 -
這樣當?
fast?到達鏈表末尾時，slow?正好指向倒數第?k?個節點。
-
-
同步移動快慢指針：
-
同時移動?
fast?和?slow，每次各移動一步，直到?fast?到達最后一個節點（fast.next == null）。
-
-
返回慢指針：
-
此時?
slow?指向的就是倒數第?k?個節點。
-
關鍵點
-
快指針先移動?
k-1?步：-
確保?
fast?和?slow?之間的間隔是?k-1。 -
例如，
k=2?時，fast?先移動 1 步，指向第 2 個節點，slow?仍在第 1 個節點，兩者間隔 1（即?k-1）。
-
-
同步移動的條件：
-
while (fast != null && fast.next != null)：-
fast != null：避免?fast?已經越界（理論上不會發生，因為題目保證?k?有效）。 -
fast.next != null：確保?fast?可以移動到下一個節點（即?fast?不是最后一個節點）。
-
-
當?
fast?是最后一個節點時（fast.next == null），循環停止，此時?slow?指向倒數第?k?個節點。
-
時間復雜度
-
O(n)，其中?
n?是鏈表的長度。-
快指針最多移動?
n?步（先移動?k-1?步，再同步移動?n-k?步）。 -
慢指針移動?
n-k?步。 -
總時間：
O(n)。
-
空間復雜度
-
O(1)，只使用了兩個指針（
fast?和?slow），沒有額外空間消耗。
public static ListNode kthToLast2(ListNode head, int k) {ListNode fast = head, slow = head;// 快指針先移動 k-1 步for (int i = 0; i < k - 1; i++) {fast = fast.next;}// 同步移動快慢指針，直到快指針到達最后一個節點while (fast != null && fast.next != null) {fast = fast.next;slow = slow.next;}return slow; // 慢指針指向倒數第 k 個節點
}
)
無網絡環境配置（詳細教程）)
