LeetCode - 876. 链表的中间结点

题目

876. 链表的中间结点 - 力扣（LeetCode）

快慢指针解法

初始化两个指针：

• 慢指针(slow)：每次移动一步

• 快指针(fast)：每次移动两步

同时移动两个指针：

• 当fast指针到达链表末尾或者倒数第二个节点时，slow指针正好位于链表的中间位置

• 如果链表长度为奇数，slow指向中间节点

• 如果链表长度为偶数，slow指向第二个中间节点

返回结果：

• 返回slow指针所指的节点

读者可能出现的错误写法

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while(fast){slow = slow->next;fast = fast->next->next;}return slow;}
};

缺少终止条件检查：

• 这个while循环只检查了fast是否为空，但没有检查fast->next

• 当fast->next为空时，访问fast->next->next会导致空指针错误

指针移动逻辑：

• 如果链表只有一个节点，fast不为空，但fast->next为空

• 此时执行fast = fast->next->next会导致空指针错误

正确的写法 

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};