LeetCode每日一练 —— 876. 链表的中间结点

前言

Wassup guys！我是Edison

今天是 LeetCode 上的 leetcode 876. 链表的中间结点

Let’s get it！

---

---

1. 题目分析

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 
如果有两个中间结点，则返回第二个中间结点。

示例 1：

示例 2：

2. 题目图解

这道题用的方法是 快慢指针法；

（1）定义慢指针 slow 一次走 1 步；
 
（2）定义快指针 fast 一次走 2 步；

奇数情况

当链表为 奇数 个时，首先，slow 和 fast 都指向第一个节点（如图所示）

然后 slow 一次走 1 步，fast 一次走 2 步，动图演示

当 fast 走到 尾节点 的时候，slow 指向的就是 中间节点

偶数情况

当链表为 偶数 个时，首先，slow 和 fast 都指向第一个节点（如图所示）

然后 slow 一次走 1 步，fast 一次走 2 步，动图演示

可以看到，当 fast 走到 NULL 时，slow 指向的就是 中间节点；

总结：

（1）当链表的节点数为 奇数 时，循环结束的条件就是 fast 走到 尾节点；
 
（2）当链表的节点数为 偶数 时，循环结束的条件就是 fast 走到 NULL；

3. 代码实现

接口代码

struct ListNode* middleNode(struct ListNode* head){
    
    struct ListNode* slow, *fast;
    slow = fast = head
    while (fast && fast->next) {
    
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

提交结果

还要注意一点：在 while 循环判断部分，写的是继续的条件，想的是结束的条件！