AcWing 33. 链表中倒数第k个节点

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 33. 链表中倒数第k个节点原题链接简单

作者：

yxc , 2019-01-06 17:27:53 , 所有人可见 , 阅读 7714

25

5

算法

(链表) $O(n)$

由于单链表不能索引到前驱节点，所以只能从前往后遍历。

我们一共遍历两次：

第一次遍历得到链表总长度 $n$；
链表的倒数第 $k$ 个节点，相当于正数第 $n - k + 1$ 个节点。所以第二次遍历到第 $n - k + 1$ 个节点，就是我们要找的答案。

注意当 $k > n$ 时要返回nullptr。

时间复杂度

链表总共遍历两次，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * 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 (n < k) return nullptr;
        auto p = head;
        for (int i = 0; i < n - k; i ++ ) p = p->next;
        return p;
    }
};

20 评论

songbiaoself 2022-07-23 16:46

快慢指针做法

 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* p, int k) {
        auto *n = p;
        while (n && k) n = n -> next, -- k;
        if (k) return nullptr;
        while (n) p = p -> next, n = n -> next;
        return p;
    }
};

安半愚 2022-08-08 20:38

牛蛙，大佬。
对了，请问下

auto *n = p;
// 换用 auto n=p;

有什么不同吗

songbiaoself 2022-08-08 20:50 回复了安半愚的评论

试了一下没区别，我习惯了c的语法，所以变量还是写了指针符号

古城萧笙 11个月前

6哦！

WANGKANG 2022-11-14 22:18

使用递归实现

class Solution {
public:
ListNode ans;
int find(ListNode p, int k) {
if(p==NULL) return 0;
int K=find(p->next, k)+1;
if(K==k) {
ans=p;
}
return K;
}
ListNode findKthToTail(ListNode pListHead, int k) {
ans=NULL;
find(pListHead, k);
return ans;
}
};

似无忌惮 2021-01-31 12:05

####按照楼上大佬Fant.J的思路写的双指针是这样的，不过复杂度和y总一样的

class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        auto p = head, q = head;
        while(k--) {
            if(p) p = p->next;
            else return NULL;
        }
        while(p) q = q->next, p = p->next;
        return q;
    }
};

acwing_64487 10个月前

为什么 p = p->next 不能用 p->val = p->next->val ; p->next = p->next->next ; 替代？

Bingxiu 2023-01-07 09:14

超简短的递归方式

    pair<int,ListNode*> fktt(ListNode* plh,int k){
        if(plh==NULL) return (pair<int,ListNode*>){0,NULL};
        pair<int,ListNode*> r=fktt(plh->next,k);
        if(r.second!=NULL) return r;
        if(r.first+1==k) return (pair<int,ListNode*>){0,plh};
        return (pair<int,ListNode*>){r.first+1,NULL};
    }
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        return fktt(pListHead,k).second;
    }