LC_面试题 02.02. 返回倒数第 k 个节点
程序员文章站
2024-03-04 10:47:05
...
解题思路
法一_双指针
- 定义两个指针指向head
- 将第一个指针做循环不断指向下一位,直至循环次数为k次
- 将两个指针同步做循环不断指向下一位,直至第一个指针为空
- 返回第二个指针所指向的值
法二_单指针(运行时间较短)
- 定义一个指针temp = head,一个常数count = 0
- 第一次用head遍历节点数时不断令count++,统计节点个数
- 第二次用temp遍历节点数,做(count-k+1)次循环
- 返回temp指向的值
提示
- 注意循环的次数
代码
法一_双指针
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode* first = head;
ListNode* second = head;
for(int i=0;i<k;i++)
{
first = first->next;
}
while(first!=NULL)
{
first = first->next;
second = second->next;
}
return second->val;
}
};
法二_单指针
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode* temp = head;
int count = 0;
while(head->next!=NULL)
{
count++;
head = head->next;
}
for(int i=0;i<count-k+1;i++)
{
temp = temp->next;
}
return temp->val;
}
};
推荐阅读
-
LC_面试题 02.02. 返回倒数第 k 个节点
-
面试题 02.02. 返回倒数第 k 个节点
-
[LeetCode]面试题 02.02. 返回倒数第 k 个节点
-
Leetcode刷题记录——面试题 02.02. 返回倒数第 k 个节点
-
LeetCode刷题记录——面试题 02.02. 返回倒数第 k 个节点
-
面试题 02.02. 返回倒数第 k 个节点
-
面试题 02.02. 返回倒数第 k 个节点
-
为面试准备,每天刷题@leetcode_面试题 02.02. 返回倒数第 k 个节点
-
面试题 02.02. 返回倒数第 k 个节点
-
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。