面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
开始的思路 ：先白遍历整个链表 然后把链表元素入栈 接着出栈k - 1 次 栈顶元素就是所求
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int kthToLast(ListNode* head, int k) {
stack<int> stk;
while (head) {
stk.push(head->val);
head = head->next;
}
for ( int i = 0; i < k - 1; ++i ){
stk.pop();
}
return stk.top();
}
};这样子 时间复杂度和空间复杂度都是O(N)的 空间消耗看着有点大
那我们就没办法了吗 有
因为所求的位置是 倒数第 k 个节点 我们可以利用双指针 定义两个指针先指向头节点 然后让一个指针先往前走k次 那么两个指针相差的位置就是k 当前面的指针走出链表 也就是指向了NULL 那么后面的指针就是指向 倒数第 k 个节点 这样子只需消耗两个指针的空间
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode *pre = head, *curr = head;
for ( int i = 0; i < k; ++i ){
curr = curr->next;
}
while ( curr ){
pre = pre->next;
curr = curr->next;
}
return pre->val;
}
};k神图解