思路:定义两个一快一慢指针,快指针每次移动两个节点,慢指针每次移动一个节点,如果相遇则说明存在环,如果快指针最后指向了NULL,则说明不存在环;
代码实现
札记之PHP实现判断一个单链表是否为回文链表
1 | class ListNode |
运行结果
1 | 2 |
参考资料:
- 快指针与慢指针之间差一步。此时继续往后走,慢指针前进一步,快指针前进两步,两者相遇。
- 快指针与慢指针之间差两步。此时唏嘘往后走,慢指针前进一步,快指针前进两步,两者之间相差一步,转化为第一种情况。
- 快指针与慢指针之间差N步。此时继续往后走,慢指针前进一步,快指针前进两步,两者之间相差(N+1-2)->N-1步。因此,此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍,所以相遇时必然只绕了一圈。