题目描述

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

注意：

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

数据范围

链表长度 $[0,30]$。

样例

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

输出：4

思路

我们会发现，倒数的第$k$个结点其实就是正数的第$len-k+1$个结点，所以我们可以先遍历一遍求长度，再遍历一遍求第$len-k+1$个结点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int len = 0;
        //不从第一个结点开始是因为当链表为空时，最后会返回一个不存在的节点，这会导致SF。
        auto p = pListHead;
        while (p) 
        {
            p = p -> next;
            len ++;
        }
        //特判长度小于k的情况
        if (len < k)
            return NULL;
        p = pListHead;
        for (int i = 1; i < len - k + 1; i ++)
            p = p -> next;
        return p;
    }
};

好了，这篇题解到这里就结束了，感谢观看，Thanks♪(･ω･)ﾉ！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$