AcWing 33. 链表中倒数第k个节点
原题链接
简单
作者:
for_sum
,
2021-08-20 17:07:37
,
所有人可见
,
阅读 170
题目描述
输入一个链表,输出该链表中倒数第 k 个结点。
注意:
k >= 1;
如果 k 大于链表长度,则返回 NULL;
数据范围
链表长度 [0,30]。
样例
输入:链表:1->2->3->4->5 ,k=2
输出:4
思路阐述及口诀
(链表) O(n)
由于单链表不能索引到前驱节点,所以只能从前往后遍历。
我们一共遍历两次:
第一次遍历得到链表总长度 n;
链表的倒数第 k 个节点,相当于正数第 n−k+1 个节点。所以第二次遍历到第 n−k+1 个节点,就是我们要找的答案。
注意当 k>n 时要返回nullptr。
时间复杂度
链表总共遍历两次,所以时间复杂度是 O(n)。
算法1
class Solution {
public ListNode findKthToTail(ListNode head, int k) {
//先遍历一遍链表,求出其长度,然后倒数第k个=正数第(n-k+1)个
int n=0;
for(ListNode p=head;p!=null;p=p.next)
n++;
if(k>n)
return null;
ListNode p=head;
for(int i=0;i<n-k;i++)
p=p.next;
return p;
}
}
算法2