141.环形链表
#链表 2024-08-07 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) { // 快慢指针，有环必相遇
                return true;
            }
        }
        return false;
    }
};

定义快慢指针：

  • 慢指针 slow：指向头节点
  • 快指针 fast：指向头节点的下一个节点（在此之前已经有判断条件，保证当前链表至少有一个节点，不会出现未定义行为）

指针的移动在 while 循环中进行，暂且不管 while 得以进行的条件，先假定作用域中的代码能够正常往下推进。先移动快慢指针，慢执行移动一个节点，快指针移动两个节点。如果两个指针指向同一个节点表明有环，如果不是就继续循环。如果最终退出循环，说明这个链表没有环。

这个时候我们再回头看 while中的条件应该怎么写？

fast 指针比 slow 指针更容易指向 nullptr，我们保证 fast 不为 nullptr 就能保证 slow 不为 nullptr。从 while 循环中的移动情况来看，fast 会移动两个节点，那我们就需要保证 fast != nullptr && fast->next != nullptr 。

为什么快慢指针能判断环形链表呢？

如果这是一条直线，快的车永远不可能遇到慢的车，如果遇到必然就是一个环。