一道字节跳动超喜欢考察的热身算法题，做不出直接淘汰

一时失言乱红尘 2023-02-25 02:08 76阅读 0赞

点击上方“**图解面试算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

大家好，我是程序员吴师兄。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 **面试题 22 . 链表中倒数第 k 个节点**，这道题在我看来是剑指 Offer 系列里面最简单的一道题，同时也是各大厂最喜欢考察的一道热身算法题。

![format_png 2][]

说内心话，如果连这道题目都做不出，那你真得关注公众号 「**图解面试算法**」和我们一起刷题了！

题目链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

### 一、题目描述 ###

输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6 。这个链表的倒数第 3 个节点是值为 4 的节点。

**示例：**

给定一个链表: 1->2->3->4->5, 和 k = 2.
    
    返回链表 4->5.

### 二、题目解析 ###

一般来说，链表相关的算法题考察的知识点有以下几个：

*  递归
 *  反转
 *  双指针
 *  环

根据我刷题的经验，如果题目中出现了 **倒数** 这个关键字，十有八九可以借助 **双指针** 来处理。

本题解题思路如下：

*  1、初始化两个指针 `former` 和 `latter`，一开始都指向链表的头节点
 *  2、前指针 `former` 先向前走 k 步
 *  3、两个指针 `former` 和 `latter` 同时向前移动，直到前指针 `former` 指向 `NULL`
 *  4、最后返回 `latter`

### 三、动画描述 ###

### 四、图片描述 ###

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

### 五、参考代码    ###

class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            //初始化两个指针 former 和 latter，一开始都指向链表的头节点
            ListNode former = head, latter = head;
            //前指针 former 先向前走 k 步
            for(int i = 0; i < k; i++){
                former = former.next;
            }
            // 两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
            while(former != null) {
                former = former.next;
                latter = latter.next;
            }
            //最后返回 latter 
            return latter;
        }
    }

### 六、复杂度分析 ###

#### 时间复杂度 ####

时间复杂度为 O(N)。

#### 空间复杂度 ####

空间复杂度为 O(1)。

### 七、相关标签 ###

*  链表
 *  双指针

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20230209/48729e2d7f814e51bead17b87dd2fb22.png
[format_png 1]: /images/20230209/ea22b777c122433fbc4937b86d867683.png
[format_png 2]: /images/20230209/fd34bf184fda4336873f2c4943cf3fd0.png
[format_png 3]: /images/20230209/f1b233d4973949b1afee7f505be6042d.png
[format_png 4]: /images/20230209/479fdc55d7c54c65baf5fb1c1d39a630.png
[format_png 5]: /images/20230209/9760a2d07b0542d99c2f374d5dde36a5.png
[format_png 6]: /images/20230209/e1121f30180644b19110b66d7798e639.png
[format_png 7]: /images/20230209/66ad1c390a724243b2df57b86c56fac8.png
[format_png 8]: /images/20230209/e4b8ffe0ebfb4ac6b2f97e6e27aa3b66.png
[format_png 9]: /images/20230209/e0e189ce55324e56b343f072e3f32744.png
[format_png 10]: /images/20230209/c7baf575c6794b06945a3918e7382d4d.png
[format_png 11]: /images/20230209/1fc5e54d7f5e43a8b720d4f480419426.png
[format_png 12]: /images/20230209/5a6d342e24344a86a95261f621056ec0.png