题目描述
输入一个链表,输出该链表中倒数第k个结点。
注意:
k >= 0;
如果k大于链表长度,则返回 NULL;
样例
输入:链表:1->2->3->4->5 ,k=2
输出:4
算法
(链表)
- 链表中倒数第k个结点,正数就是第
n - k + 1
,因为是从head
开始,所以向后n - k
步就可以。又因为下标从0开始,所以是i < n - k
。我一开始傻了,以为n - k
的前面是n - k + 1
,其实是n - k - 1
,又因为从0开始,go
指针的初值是head
,所以向后n - k
步即可。
时间复杂度
$O(n)$
链表总共遍历两次,2n
,所以时间复杂度是$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 cur = head; cur; cur = cur->next) n ++;
if(k > n) return NULL;
auto go = head;
for(int i = 0; i < n - k; i ++) go = go->next;
return go;
}
};