力扣 – 劍指 Offer 22. 鏈表中倒數第k個節點

• 2021 年 11 月 19 日
• 筆記
• 雙指針, 回溯, 差值法, 棧, 演算法與題解, 遞歸, 鏈表

題目

劍指 Offer 22. 鏈表中倒數第k個節點

思路1（棧）

• 既然要倒數第k個節點，那我們直接把所有節點放到棧（先進後出）裡面，然後pop彈出k個元素就可以了

程式碼

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        LinkedList<ListNode> stack = new LinkedList<>();

        // 把整個鏈表入棧
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 先將前n-1個元素出棧
        for (int i = 1; i < k; i++) {
            stack.pop();
        }

        // 此時位於棧頂的就是倒數第k個元素啦
        return stack.pop();
    }
}1

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(N)\)，使用棧的額外空間要花掉\(O(N)\)

思路2（遞歸+回溯）

• 和使用棧的思想差不多。。
• 先遞歸到鏈表末尾，然後依次回溯，回溯k次的時候就得到我們需要的節點了

程式碼

class Solution {
    ListNode res;
    // 代表當前處於倒數第幾個節點
    int cur = 0;

    public ListNode getKthFromEnd(ListNode head, int k) {
        dfs(head, k);
        return res;
    }

    public void dfs(ListNode node, int k) {
        // 先遞歸到末尾
        if (node == null) {
            return;
        }

        dfs(node.next, k);

        // 倒數第cur個節點
        cur++;
        // 等於k代表找到了
        if (cur == k) {
            res = node;
        }
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(N)\)，需要遞歸整個鏈表

思路3（雙指針）

• 定義fast快指針和slow慢指針兩個指針：讓快指針fast先走k步，然後再讓兩個指針同時移動，等快指針fast走道鏈表末尾時候（為null），此時慢指針slow所指向的節點就是倒數第k個節點

程式碼

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 讓快指針先走k步，和慢指針相差k個距離
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此時讓慢指針和快指針同時走，知道快指針到達鏈表末尾為null時，慢指針就在倒數第k個位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指針即為答案
        return slow;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)

思路4（差值法）

• 因為要求的是倒數第k個節點，那如果我們知道了鏈表的總長度，那麼這個節點在鏈表中的順序位置也就知道了
• 先計算出鏈表的總長度，則可以得出：倒數第k個節點 等於 鏈表總長度-k+1。但是在題目中我們已經指向了鏈表的第一個節點，所以只需要再走n-k個節點即可到達倒數第k個節點

程式碼

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int length = 0;
        ListNode p = head;

        // 先獲取鏈表的總長度
        while (p != null) {
            p = p.next;
            length++;
        }

        // 其實倒數第k個的位置就相當於 length-k
        // 然後我們從鏈表頭部開始遍歷 length-k 個節點，此時所在的節點位置就是答案了
        k = length - k;
        for (int i = k; i > 0; i--) {
            head = head.next;
        }
        
        return head;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)