【手撕OJ题】——876. 链表的中间结点

🕒 题目

🔎 876. 链表的中间结点【难度：简单🟢】
给你单链表的头节点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

• 示例 1：
  

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

• 示例 2：
  

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

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

⌛ 方法① - 直接遍历

💡 思路：遍历两遍数组，第一遍求出链表长度，第二步找出链表的中间节点并返回。

代码实现如下：

struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur = head;int count = 0;// 第一次遍历：计算链表长度while(cur){count++;cur = cur->next;}// 计算中间节点的位置cur = head;count /= 2;// 第二次遍历：找到中间节点while(count--){cur = cur->next;}return cur;
}

⌛ 方法② - 快慢指针

💡 思路：一次遍历即可找到中间节点。定义两个指针 fast 和 slow，slow指针每次移动一步，而fast指针每次移动两步。
当链表长度为奇数，fast到达链表末尾时（即fast->next == NULL）时，slow 为中间节点；当链表长度为偶数，fast == NULL 时，slow 为中间节点。

struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow, *fast;slow = fast = head;//注意：while条件中fast一定要写前面，否则偶数个时fast->next会造成空指针解引用while(fast && fast->next)  //节点是奇数还是偶数未知{slow = slow->next;fast = fast->next->next;}return slow;
}

---

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页