AcWing 33. 链表中倒数第k个节点
原题链接
简单
作者:
andream7
,
2020-12-23 12:41:20
,
所有人可见
,
阅读 305
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* head, int k) {
int n = 0;
// 求出链表长度
for (auto p = head; p; p = p->next){
n++;
}
if (k > n) return NULL;
auto p = head;
// 倒数第k个就是第n - k + 1 个
for (int i = 0; i < n - k; i ++){
p = p->next;
}
return p;
}
};
快慢指针的做法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* head, int k) {
auto first = head, second = head;
while(k -- && first) {
first = first->next;
}
// 如果此时k>=0,说明k大于链表长度,返回空
if (k >= 0) return NULL;
//两个指针同时后移,first移动到末尾时,second刚好指向倒数第k个结点
while(first) {
first = first ->next;
second = second ->next;
}
return second;
}
};