题解 | #判断链表中是否有环#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    bool hasCycle(ListNode* head) {
        ListNode* p1 = new ListNode(0);
        ListNode* p2 = new ListNode(0);

        p1 = head;
        p2 = head;
        int r = 0;
        int randomnum;
        while (p2 != nullptr) {
            srand(r);
            randomnum = rand();
            if (randomnum % 2 && r != 0) {
                p1 = p1->next;
            }
            p2 = p2->next;
            if (p2 == nullptr) return false;
            if (p1 == p2) return true;
            r++;
        }
        return false;
    }
};

这叫简单？想了我老半天，恕臣愚钝。一开始总是想着随机在链表某处做断点，看是否会回到断点处。想了半天才想到用双指针追赶的办法。

以上代码思路如下：设置两个指针，初始都指向头节点，然后指针p2每次移动一步，而指针p1第一回合先不移动，之后每个回合都给指针p1一个随机数，根据随机数决定要不要动。最后如果有环，那么p2一定会追上p1；如果没有环，则p2最终会等于null。