跟着姚桑学算法-链表中倒数第k个节点

题.链表中倒数第k个节点

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

注意：
k >= 1;
如果 k 大于链表长度，则返回 NULL;

数据范围
链表长度 [0,30]。

样例

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

输出：4

【题解】-- 双指针扫描

由于单链表不能索引到前驱节点，所以只能从前往后遍历。

我们一共遍历两次：

• 第一次遍历得到链表总长度 n；
• 链表的倒数第 k 个节点，相当于正数第 n−k+1 个节点。所以第二次遍历到第 n−k+1 个节点，就是我们要找的答案。

注意当 k>n 时要返回nullptr。

复杂度分析：

链表总共遍历两次，所以时间复杂度是 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 (n < k) return nullptr;
        auto p = head;
        for (int i = 0; i < n - k; i ++ ) p = p->next;
        return p;
    }
};