leetcode -- 876.链表的中间节点

🐨1.题目

给你单链表的头结点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

🐇2. 解法1-两次遍历

🍀2.1 思路

该题没有对时间复杂度和空间复杂度作出要求，那么最直接的思路就是将链表遍历2遍：

• 第一次遍历：统计链表元素个数n。
• 第二次遍历：遍历到n/2个元素(链表首节点为第0个元素)。

🍀2.2 代码实现

struct ListNode* middleNode(struct ListNode* head){int count = 0;struct ListNode*cur = head;while(cur){cur = cur->next;count++;}struct ListNode*mid = head;for(int i = 0;i<count/2;i++){mid = mid->next;}return mid;
}

🐁3. 解法2-快慢指针

🌾3.1 思路

既然是找中间节点，那么不妨设置两个指针：

• 一个快指针fast，每次走2步；
• 一个慢指针slow，每次走1步。

那么当快指针走完的时候，慢指针正好是走到中间元素

如图所示：
我们这里需要判断结束的条件是当fast == NULL或者fast->next == NULL

🌾3.2 代码实现

struct ListNode* middleNode(struct ListNode* head){struct ListNode*fast = head;struct ListNode*slow = head;//这里要先判断fast，再判断fast->next，顺序不可写反while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

🐮4. 题目链接

leetcode – 876.链表的中间节点