网站文章收录深圳招工包吃住8000元
876. 链表的中间结点
- 算法 = 快慢指针 & 题目特征 = 需要对链表中的节点进行遍历，并且需要根据节点之间的相对位置或者距离进行操作
题目链接：https://leetcode.cn/problems/middle-of-the-linked-list/
算法 = 快慢指针 & 题目特征 = 需要对链表中的节点进行遍历，并且需要根据节点之间的相对位置或者距离进行操作
思路：用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow, head = nullptr;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}
};
细节处理：如果有两个中间结点，则返回第二个中间结点。
对于一个偶数长度的链表，假设链表中有 6 个节点，节点分别为 1 -> 2 -> 3 -> 4 -> 5 -> 6。
当 slow 和 fast 初始都指向链表的头节点时，slow 每次移动一步，fast 每次移动两步。
- 第一步：slow 移动到节点 2，fast 移动到节点 3。
- 第二步：slow 移动到节点 3，fast 移动到节点 5。
- 第三步：slow 移动到节点 4，fast 移动到节点 6。
此时，fast 到达了链表的末尾，slow 位于链表的中间位置，即节点 4。
根据这个例子，我们可以看到，当链表长度为偶数时，slow 确实返回的是中间的第二个节点，即节点 4。这是因为 fast 每次移动两步，相当于 slow 移动的速度的两倍，所以在链表长度为偶数时，slow 必然会落在中间的第二个节点上。
如果希望返回中间的第一个节点，可以在初始化时让 fast 指向链表的第一个节点，然后进行相同的遍历操作。这样，当 fast 到达链表的末尾时，slow 就会指向中间的第一个节点。
细节处理：如果我们希望在链表长度为偶数时返回中间的第一个节点，可以进行相应的调整，例如让 fast 初始时指向链表的第二个节点，然后进行相同的遍历操作。这样，当 fast 到达链表末尾时，slow 就会指向中间的第一个节点。
对于一个偶数长度的链表，假设链表中有 6 个节点，节点分别为 1 -> 2 -> 3 -> 4 -> 5 -> 6。
当 slow 初始指向链表的头节点，fast 初始指向链表的第二个节点时，slow 每次移动一步，fast 每次移动两步。
- 第一步：slow 移动到节点 1，fast 移动到节点 3。
- 第二步：slow 移动到节点 2，fast 移动到节点 5。
- 第三步：slow 移动到节点 3，fast 移动到节点 6。
此时，fast 到达了链表的末尾，slow 位于链表的中间位置，即节点 3。
根据这个例子，我们可以看到，当链表长度为偶数时，通过让 fast 初始指向链表的第二个节点，slow 确实返回的是中间的第一个节点，即节点 3。
所以，通过调整 fast 初始位置，我们可以控制在链表长度为偶数时返回中间的第一个节点还是第二个节点。