【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点

🌈个人主页：聆风吟
🔥系列专栏：数据结构、算法模板
🔖少年有梦不应止于心动，更要付诸行动。

---

📋前言

    💬 hello! 小伙伴们大家好哇，今天作者给大家带来的是链表的相关面试题的讲解，在学习了下文之后，相信大家可以更好的理解链表，并且我们同过本文的练习相信大家对快慢双指针也将会有一定的了解。
    📚 系列专栏：本期文章收录在《剑指offer每日一练》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝！

---

一. ⛳️链表的中间结点

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

题目：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例：

输入： head = [1,2,3,4,5]
输出： [3,4,5]
解释： 链表只有一个中间结点，值为 3

限制：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

解题思路：
暴力求解（不推荐）
拿到本题我们很容易想到一种方法就是：遍历整个链表，记录整个链表的元素个数count，然后求出中间结点的位数cout/2 + 1，最后从头开始遍历链表到cout/2 + 1位置的结点，返回该结点即可。显然该方法是比较慢的，那么有没有更好的方法呢？当然是有的，我们可以借助快慢双指针进行快速求解。

快慢双指针（推荐）
创建快慢双指针 slow 和 fast 分别指向链表的头部，循环执行：

• 快指针 fast 每轮走两步；
• 慢指针 slow 每轮走一步；

这样 fast 的步数恒为 slow 的 2 倍，因此当快指针遍历完链表时，慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点，因此需要分两种情况考虑：

• 链表的长度为奇数：当 fast 走到链表的尾结点时，slow 正好是中间结点；
• 链表的长度为偶数：当 fast 为空（越过尾结点）时，slow 正好走到第二个中间结点。

总结以上规律，应在当 fast 遇到或越过尾节点时跳出循环，并返回 slow 即可。

示例动图展示：

c代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    //创建快慢指针
    struct ListNode* slow = head, *fast = head;

    //循环执行
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    //返回中间结点
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

二. ⛳️链表中倒数第k个结点

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

题目：
输入一个链表，输出该链表中倒数第k个结点。

示例：

输入： 1,{1,2,3,4,5}
输出： {5}

解题思路：
快慢双指针
学习了上题相信大家对快慢双指针已经有了一定了解。本题我们可以先创建快慢双指针 slow 和 fast 分别指向链表的头部：

1. 先让快指针fast 先向后走k 步；
   注意：当fast向后走的过程中，fast提前为空，说明链表的长度没有 k 大，需要终止程序，返回结果NULL。
2. 然后快指针fast 和慢指针slow 一起循环向后走；
3. 直到fast为空时终止循环，返回slow即可。

示例动图展示：

c代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here

    //创建快慢双指针 slow 和 fast 分别指向链表的头部
    struct ListNode* slow = pListHead, *fast = pListHead;

    //先让快指针fast 先向后走 k 步
    for(int i = 0; i < k; i++)
    {
        //如果fast提前为空，需要终止程序，返回结果NULL
        if(fast == NULL)
        {
            return NULL;
        }

        fast = fast->next;
    }

    //快指针fast 和慢指针slow 一起循环向后走
    //fast为空时终止循环
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    //返回
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

📝结语

     今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！