c++中如何实现快慢指针_c++链表找中点或判断环的方法【详解】_技术教程

快慢指针用两个 ListNode* 指针手动模拟：slow每次走1步，fast每次走2步；需先判fast和fast->next非空再执行fast->next->next，初始化均为head，空链表直接安全退出。

快慢指针在 C++ 链表中怎么写

快慢指针不是库函数，而是用两个 ListNode* 指针变量手动模拟的双指针技巧。核心是：慢指针每次走 1 步（slow = slow->next），快指针每次走 2 步（fast = fast->next->next）。必须确保 fast 和 fast->next 非空才执行第二步，否则会触发 nullptr->next 段错误。

典型初始化写法：

ListNode* slow = head;
ListNode* fast = head;

注意：起点都设为 head 是通用做法；若链表为空（head == nullptr），循环不进，直接返回，无需额外判空。

找单链表中点时 slow 最终停在哪

取决于链表长度奇偶性，但 slow 总是指向「中间偏左的那个节点」：

长度为奇数（如 5）→ slow 停在第 3 个节点（严格中点）
长度为偶数（如 4）→ slow 停在第 2 个节点（前一个中点）

这是由终止条件决定的：while (fast != nullptr && fast->next != nullptr)。当 fast 到达末尾或倒数第二个节点时退出，此时 slow 走了约一半步数。

如果需要「后一个中点」（比如做归并排序切分），可改用：while (fast->next != nullptr && fast->next->next != nullptr)，然后让 slow = slow->next 再走一步——但多数场景用默认逻辑即可。

判断链表是否有环为什么能用快慢指针

本质是追及问题：若存在环，快指针终将从后面追上慢指针；若无环，快指针先到达 nullptr。

关键细节：

必须用 do-while 或先移动再判断，避免初始时 slow == fast 的假阳性（起点相同）

推荐写法：

if (!head || !head->next) return false;
ListNode* slow = head;
ListNode* fast = head;
do {
    slow = slow->next;
    fast = fast->next->next;
} while (fast && fast->next && slow != fast);
return slow == fast;

循环内必须检查 fast 和 fast->next 是否非空，否则 fast->next->next 可能崩溃
环入口点的定位需额外步骤（Floyd 算法第二阶段），不在基础判断范围内

容易被忽略的边界和性能影响

快慢指针本身时间复杂度 O(n)、空

间 O(1)，但实际使用时几个坑常导致 crash 或逻辑错：

fast->next->next 前没确认 fast->next 存在 → 段错误
把 while (fast != nullptr && fast->next != nullptr) 错写成 && 顺序颠倒（C++ 短路求值，必须先判 fast 再判 fast->next）
对空链表或单节点链表未做前置保护，直接解引用 head->next
在找中点后拆链时，忘记把前半段尾节点的 next 设为 nullptr，导致后续遍历成环