方法一：遍历

为了知道链表长度，先遍历一遍，倒数第k个节点即正数第n-k个节点。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int n = 0;

        for (auto p = head; p; p = p->next) n ++ ;              //为了得到链表长度需要遍历一次

        if (k > n) return NULL;                                 //k大于链表长度则无此节点

        for (int i = 0; i < n - k; i ++ ) head = head->next;    //倒数第k个节点即正数第n-k个节点

        return head;
    }
};

方法二：快慢指针

快指针先走k步，然后快慢指针同时走，快指针走到链表尾部时慢指针指向的即是倒数第k个节点。

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

        while (k -- ) fast = fast->next;
        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

解法三：真正鲁棒的解法

以上两种解法从逻辑上看都没有问题，但鲁棒性太差，比如链表长度为3，要求倒数第5个节点，程序便会崩溃。而且也没有判断链表为空和k为0时的特殊情况。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if (!head || k == 0) return nullptr;             //判空及倒数第0个节点
        auto fast = head, slow = head;

        while (k -- ) 
        {
            if (!fast->next) return nullptr;            //链表长度小于k的情况
            fast = fast->next;
        }
        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

这才是面试官真正想看到的解法。