2021-01-24 | 劍指 Offer 22. 連結清單中倒數第k個節點

1. 題目描述

輸入一個連結清單，輸出該連結清單中倒數第k個節點。為了符合大多數人的習慣，本題從1開始計數，即連結清單的尾節點是倒數第1個節點。

例如，一個連結清單有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6。這個連結清單的倒數第 2 個節點是值為 4 的節點。

示例：

給定一個連結清單: 1->2->3->4->5, 和 k = 2.
傳回連結清單 4->5.      

2. 解題思路

對于這個題目，我們可以使用快慢指針來解決，初始化slow和fast兩個指針，開始時兩個指針都在連結清單的頭部。

首先讓快指針fast先走，向後走k個節點，這樣快指針和慢指針之間就相差k個節點。之後，兩個指針同時向後移動，知道快指針移動到最後一個節點。這時，由于快慢指針之間相差k個節點，是以此時慢指針所指向的節點就是倒數第k個節點。

• 時間複雜度：O(n)，其中n是連結清單的長度，我們需要周遊整個連結清單；
• 空間複雜度：O(n)，其中n是連結清單的長度，我們需要儲存快慢兩個指針指向的連結清單；

3. 代碼實作

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let slow = head, fast = head;
    let cur = 0;
    while(cur < k){
        fast = fast.next
        cur++
    }

    while(fast){
        fast = fast.next
        slow = slow.next
    }
    return slow

};      

4. 送出結果