题目描述
输入一个链表，输出该链表中倒数第 k 个结点。
注意：
k >= 1;- 如果 k 大于链表长度，则返回 NULL;
数据范围
链表长度 [0,30]。
样例
输入：链表：1->2->3->4->5 ，k=2 输出：4
方法一：链表 O(n)
思路，我们拿样例 1->2->3->4->5 且 k = 2 来举例：
- 先遍历一遍链表得到链表长度
n即n = 5。 - 然后得到倒数第
k个结点的位置是链表正数第n - k + 1个结点，即5 - 2 + 1 = 4，也就是最终返回第四个结点4。
/** * 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 n = 0; for (ListNode* p = pListHead; p; p = p->next) n++; if (k > n) return NULL; ListNode* q = pListHead; for (int i = 0; i < n - k; i++) q = q->next; return q; } };
欢迎大家在评论区交流~
