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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <iostream>
#include <unistd.h>
#include <vector>
class Solution {
  public:
    bool hasCycle(ListNode* head) {
        vector<ListNode*> addr;
        while (head!=nullptr) {
            if (head->next==nullptr) {
                return false;
            }
            if (count(addr.begin(), addr.end(), (head))) {
                return true;
            }
            addr.push_back(head);
            head = head->next;
        }
        return false;
    }
};

时间复杂度O（n），空间复杂度O（n）。

1.新建一个vector，内部变量类型为节点类，循环往里放节点；

2.判断是否有重复的节点，有的话，则返回true

3.没环则返回false -----确实没环，只有一个节点且没环