題目描述

輸入一個鏈表，輸出該鏈表中倒數第 k 個結點。
時間限制：1 秒 空間限制：32768K
本題知識點： 鏈表

代碼實現

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode node = head, temp = head;
        int i = 0;
        for(; node != null; i++){
            if(i >= k){
                temp = temp.next;
            }
            node = node.next;
        }
        return k > i ? null : temp;
    }
}

解題思路

首先我們要知道什么是鏈表，可以通過參考文章底部的推薦文章進行了解。簡單來說就是它有一系列結點組成，每個結點包括一個數據結構（用來存放各類型的數據），還包括一個指向下一個結點的指針。

因為題中給出的鏈表為單鏈表，每個結點只有下一個結點的指針，而沒有前一個結點的指針，所以我們要想知道倒數第 k 個結點，我們首先需要從第一個結點開始一直找到最后一個結點，得到共有多少個結點，然后再算出倒數第 k 個結點是整數第幾個結點，然后再從第一個結點開始直到找到最終要找的結點。

但是我們這里使用的方法很巧妙，我們定義兩個指針都指向第一個結點，然后讓其中一個指針 node 先走 k 步，然后 temp 指針再開始走，直到 node 走到最后，因為 node 比 temp 始終快 k 步，所以最后 temp 指向的結點就是倒數第 k 個結點，不過這里有個前提就是 k 不能大于我們所有結點的總數，如果大于的話，是沒有倒數第 k 個結點的，所以返回空。