面试题 02.02. 返回倒数第 k 个节点

https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

实现一种算法，找出单向链表中倒数第 $k$ 个节点。返回该节点的值。
注意：本题相对原题稍作改动

示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：给定的 $k$ 保证是有效的。

又是鏈結串列題（鏈表），拿到題之後我第一次的想法是先找到尾節點 tail，遍歷找到之後發現這是個單鏈表根本就沒有前驅……

然後我思考了一下，想到了 $「統計鏈表長度」$ 的解法。
可以先遍歷鏈表統計出鏈表結點個數，將鏈表長度記爲 $N$，然後再用給定的 $k$ 與之相減，得到的值 ($step$) 就是抵達欲返回的結點的步數：
$$step=N-k$$
然後只需要循環走 $step$ 步，即可找到倒數第 $k$ 個結點了。

程式如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        int count = 0;
        struct ListNode* cur = head;      // 遍歷鏈表
        while (cur->next != nullptr) {
            count++;
            cur = cur->next;
        }

        int n = count - k;   // 計算第幾個
        cur = head;
        while (n >= 0) {
            cur = cur->next;
            n--;
        }
        return cur->val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

當然這裏可以使用更高級的 $「快慢指標法」$，可以省掉統計鏈表長度的過程。具體方法如下：

1. 定義兩個指標，分別為快指標 fast 和慢指標 slow，並初始化為 head。
2. 先令快指標 fast 先走 $k$ 步，此時 fast 和 slow 的距離差為 $k$。
3. 再令快指標和慢指標一起走，直到快指標 fast 碰到 nullptr 爲止。

循環結束後，神奇的一幕發生了（其實一點都不神奇），slow 指向的就就是「倒数第 $k$ 個結點」了，返回 slow 即可。
程式如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;

        // 快指標先走
        for (int i = 0; i < k; i++) {
            fast = fast->next;
        }

        // 快慢指標一起走
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow->val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

時間複雜度為 $O(n)$，其中 $n$ 為鏈表長度。