题目描述

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

样例

如：一个链表有6个节点，从头节点开始，它们的值一次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

直接遍历

因为是单向链表，所以无法从后向前遍历；
一种直观的思路是先遍历链表得到链表的长度，然后第二次遍历就能找到第k个节点。

C++ 代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* head, unsigned 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;
    }
};