剑指 Offer 22. 链表中倒数第k个节点

末蓝、 2024-04-20 07:23 1阅读 0赞

⭐**简单说两句**⭐

> **CSDN**个人主页：[后端小知识][Link 1]
> 
> 🔎**GZH**：`后端小知识`
> 
> 🎉欢迎关注🔎点赞👍收藏⭐️留言📝

题目： 剑指 Offer 22. 链表中倒数第k个节点  ，我们今天来看一道**easy**的题目吧，这是选自**剑指Offer**上的一道题，好了，我们一起来看看题意吧：

考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接题目链接放下面！

1.  题目传送门：

[剑指 Offer 22. 链表中倒数第k个节点][Offer 22. _k]

![image-20230212164446791][]

`思路`:

**朴素版：**

我们可以先直接遍历链表，获取总长度，记为len, 那么在从头开始遍历 len-k次，下一个节点就是答案

**优化版：**

我们其实也可以采用双指针的方式来操作（相当之科学）😉

前指针先往前走k下，然后前指针走一步，后指针就走一步（第一步是从头结点开始的），当前指针指向NULL的时候，这时后指针也就刚刚好到了倒数第k个节点的位置

![image-20230212171751423][]

`我们来看看成功AC的代码吧：`

/**
     * 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) {
        
            //p1为前指针，p2为后指针
            ListNode* p1=head;
            ListNode* p2=head;
            //p1指针先走k步
            for(int i=0;i<k;i++) p1=p1->next;
            //p1不为空时，p1走一步，p2走一步，p1为空时，p2这是就是结果
            while(p1!=NULL){
        
                p1=p1->next;
                p2=p2->next;
            }
            return p2;
        }
    };

小总结：这道题整体来看还是**很简单**的，优化版的这种思路也是很容易理解的，虽然不容易想到😂

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!

💬

**CSDN**个人主页：[后端小知识][Link 1]

🔎**GZH**：`后端小知识`

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

[Link 1]: https://blog.csdn.net/m0_46833224
[Offer 22. _k]: https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/?favorite=xb9nqhhg
[image-20230212164446791]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a373a423b4474719853b918a6ba35b6d.png
[image-20230212171751423]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/da83a6f691514a2ba2c3b36af4af8499.png