当前位置:网站首页>【每日一题】【leetcode】26. 链表-链表中倒数第k个节点
【每日一题】【leetcode】26. 链表-链表中倒数第k个节点
2022-08-10 15:04:00 【aneutron】
题目
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 难易程度:easy
示例 1:
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
分析
本题典型的双指针题目:
- 设指针
rp
、lp
都指向head
, rp
先走k
步rp
、lp
同步移动- 到
rp
指向链表尾后NULL
的时候,lp
即是倒数第k
个节点
时间复杂度:O(N) 空间复杂度:O(1)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *lp = head, *rp = head;
while (rp != NULL) {
rp = rp->next;
if (k > 0) {
k--;
} else {
lp = lp->next;
}
}
return lp;
}
};
上述算法,可以进一步优化,rp
只先走k-1
步,最后rp
指向链表的最后一个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *lp = head, *rp = head;
while (rp->next != NULL) {
rp = rp->next;// 结束时,rp是最后一个节点,而非NULL
if (k > 1) {
k--;
} else {
lp = lp->next;
}
}
return lp;
}
};
边栏推荐
猜你喜欢
Redis -- Nosql
“低代码”编程或将是软件开发的未来
26、压缩及解压缩命令
E. Cross Swapping (and check out deformation/good questions)
JS entry to proficient full version
Recommend a few had better use the MySQL open source client, collection!
Oracle数据库备份dmp文件太大,有什么办法可以在备份的时候拆分成多个dmp吗?
使用 ABAP 正则表达式解析 uuid 的值
软件测试用例篇
Allwinner V853 development board transplants LVGL-based 2048 games
随机推荐
SWIG tutorial "four" - package of go language
Based on Azuki Series: NFT Valuation Analysis Framework "DRIC"
How to code like a pro in 2022 and avoid If-Else
数据在内存中的存储
An ABAP tool that can print the browsing history of a user in the system for BSP applications
SWIG教程《二》
Detailed understanding of all built-in functions (Part 2)
Introduction to the Internet (2)
$'\r': command not found
SYM32——RTC实时时钟程序讲解
Mobileye携手极氪通过OTA升级开启高级驾驶辅助新篇章
Oracle database backup DMP file is too big, what method can be split into multiple DMP when backup?
SWIG tutorial "two"
Pagoda panel open Redis to specify the network machine
Basic learning of XML
软件测试用例篇
Appium进行APP自动化测试
请查收 2022华为开发者大赛备赛攻略
E. Cross Swapping (and check out deformation/good questions)
Understanding_Data_Types_in_Go