[链表OJ题 2] 链表的中间结点 -- 快慢指针找链表的中间节点

╰半夏微凉° 2023-09-27 19:26 96阅读 0赞

**目录**

题目来源：

代码实现

思路分析：

1.当链表个数为奇数

2.当链表个数为偶数

总结：

--------------------

## 题目来源： ##

[876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)][876. _ - _LeetCode_ _leetcode-cn.com]

**题目描述：**

![ea7b31328813cd6c5cc7540132cb0562.png][]

## 代码实现 ##

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.当链表个数为奇数 ####

![273a50c53037754ca05ef2a467a14d6b.png][]

我们使用快慢指针，并规定 fast 指针每次走两步，slow 指针每次走一步，当 fast->next = NULL 时，slow 刚好指向的就是中间结点。

#### 2.当链表个数为偶数 ####

![05c0e8af7aec5789e8ef6cb9ea437052.png][]

根据题意，当链表个数为偶数的时候，存在两个中间结点，返回第二个中间节点。我们使用快慢指针，并规定 fast 指针每次走两步，slow 指针每次走一步，当 fast = NULL 时，slow 刚好指向的就是第二个中间结点。

## 总结： ##

当 fast = NULL 或者 fast->next = NULL 时，slow 指针指向的就是中间结点。

**注意：**

while(fast && fast->next)，括号内的判断条件顺序是不能换的，因为 && 操作符在执行的时候是有先后顺序的，先执行左边，再执行右边。当链表的个数为偶数的时候，fast最后会直接走到 NULL，要是将 fast->next 放在 && 左边，会被先执行，这样就会导致空指针异常的情况。

![ecd710b48e49e65d291212b1a6f91b97.png][]

\*\*\* 本篇结束 \*\*\*

[876. _ - _LeetCode_ _leetcode-cn.com]: https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
[ea7b31328813cd6c5cc7540132cb0562.png]: https://img-blog.csdnimg.cn/img_convert/ea7b31328813cd6c5cc7540132cb0562.png
[273a50c53037754ca05ef2a467a14d6b.png]: https://img-blog.csdnimg.cn/img_convert/273a50c53037754ca05ef2a467a14d6b.png
[05c0e8af7aec5789e8ef6cb9ea437052.png]: https://img-blog.csdnimg.cn/img_convert/05c0e8af7aec5789e8ef6cb9ea437052.png
[ecd710b48e49e65d291212b1a6f91b97.png]: https://img-blog.csdnimg.cn/img_convert/ecd710b48e49e65d291212b1a6f91b97.png