【数据结构与算法面试题】单向链表倒数第k个节点
这里写图片描述
问题分析：遍历一遍链表的时间复杂度为O(n)，但是链表节点的遍历只能按顺序遍历，问题中是需要取到倒数第k个，最直接的想法是遍历两遍链表，第1遍得到链表的长度，第2遍是取到倒数第k个；那么能否只遍历一遍就能取到倒数第k个节点，最关键的点是需要确定链表的长度，我们可以使用双指针的方法：第一个指针用于遍历整个链表，第二个链表用于遍历部分链表，第一个指针比第二个指针多走k步，当第一个指针遍历完链表，第二个指针所指的即为倒数第k个数，如下图所示：
这里写图片描述
方法：
ListNode* get_reverse_k(ListNode *head, int k){
if (NULL == head) return NULL;
ListNode *p = head;
ListNode *q = head;
int step = 0;
while (NULL != p->m_pNext){
if (step >= k){
q = q->m_pNext;
}
p = p->m_pNext;
step ++;
}
if (step < k) return NULL;
else return q;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/06/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
