题目描述

输入一个链表，输出该链表中倒数第k个结点。

注意：

• k >= 0;
• 如果k大于链表长度，则返回 NULL;

样例

输入：链表：1->2->3->4->5 ，k=2

输出：4

算法

(链表) $O(n)$

1. 因为链表不能从后往前遍历，所以需要先计算链表长度 n
2. 倒数第 k 个节点就是顺数第 n - k + 1 个节点

注意：如果 k 大于链表长度则直接返回空

时间复杂度

遍历链表求长度的时间复杂度为 $O(n)$，找第 n - k + 1 个节点的时间复杂度也是 $O(n)$，所以总时间复杂度为 $O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;

        if (k > n) return nullptr;

        auto p = head;
        for (int i = 0; i < n - k; i ++ ) p = p->next;
        return p;
    }
};