🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。
🚁 个人主页:不 良
🔥 系列专栏:🛸剑指 Offer 🛹Linux
📕 学习格言:博观而约取,厚积而薄发
🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同成长! 🌹
剑指 Offer 22. 链表中倒数第k个节点
题目:
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例如,一个链表有
6
个节点,从头节点开始,它们的值依次是1、2、3、4、5、6
。这个链表的倒数第3
个节点是值为4
的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
思路一:
1.先定义一个节点
cur
,cur = head
,然后向后遍历一遍链表,算出链表中元素个数count
,如果链表为空,则直接返回nullptr
;2.链表的尾节点是倒数第1个节点,那么倒数第k个节点从头节点开始数也就是第
count - k
个节点;3.再让
cur = head
,从头开始遍历找到第count - k
个节点,返回第count - k
个节点就是链表中倒数第k
个节点。
代码如下:
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//头节点为空,直接返回
if(head == nullptr)
return nullptr;
ListNode* cur = head;
int count = 0; //记录链表中结点个数
//遍历统计链表个数
while(cur)
{
cur = cur->next;
count++;
}
int n = count - k;
cur = head;
//从头开始遍历n个节点
while(cur && n-- )
{
cur = cur->next;
}
return cur;
}
};
时间复杂度:
O(N)
空间复杂度:
O(1)
文章来源地址https://www.toymoban.com/news/detail-504933.html
思路二:
双指针法。
1.设置快慢指针
fast
和slow
,让fast = head; slow = head
;2.让
fast
指针先向后走k
步,然后fast
指针和slow
指针同时向后走;3.当
fast
指针为空时,slow
即是链表中倒数第k
个节点。总体看,
fast
走了N
步,slow
走了N-k
步。
代码如下:
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//头节点为空
if(head == nullptr)
return nullptr;
ListNode* fast = head;
ListNode* slow = head;
//先让fast指针向前走k步
while(fast && k--)
{
fast = fast->next;
}
//然后让fast和slow同时向后走,当fast为空时,slow即为链表中倒数第k个节点
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
时间复杂度:
O(N)
文章来源:https://www.toymoban.com/news/detail-504933.html空间复杂度:
O(1)
到了这里,关于剑指 Offer 22. 链表中倒数第k个节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!