判断链表是否有环--三种思路

0x01.问题

给定一个链表，判断链表中是否有环。
注：这个环可以是尾节点连接到前面的任意一个节点

0x02.分析三种方法

第一种：哈希表

最容易想到的，就是每遇到一个节点，如果不存在，就把它存入哈希表，存在就直接返回true。没有一个重复的就返回false。

注意：

• 最好使用unordered_set，而不是set，更节省时间。
• 存的数据类型一定要是指针，不能是值，因为值可能存在相同的。

优劣势分析：

• 空间换取时间，只进行依次遍历，但多使用了一个链表的空间。
• 时间复杂度为：O（N）。
• 空间复杂度为：O（N）。

第二种：快慢双指针

这是一个常识，如果在一个环形跑道上赛跑，快的人和慢的人一定会相遇。所以我们可以使用一个快指针，每次走两步，一个慢指针，每次走一步，如果存在环，一定会相遇，如果快指针遇到空了，就说明没有环。

注意：

• 初始化时快指针应该是head->next。

优劣势分析：

• 以时间换取空间，不过时间消耗的也不多，进环的时候，迭代次数会多一些。
• 时间复杂度：O（N+K），K为环的长度。
• 空间复杂度：O（1）。没有使用额外的空间。

附加：如果需要返回成环的那个节点，我们只需要找到快慢指针相遇的点，用指针p代替，然后再用一个指针指向头指针，用q代替，每次同时将它们挪动一步，直到它们相遇，它们相遇的点就是环的入口！这里省略数学证明，这其实也是Floyd算法的一种应用。

第三种：标志法

我们可以给每个访问过变量记上一个标记，如果下次仍然发现了这个标记，说明肯定成环。

常见的标价法是改变自身的值，通常为一个大数，表示一般不可能取到的值，当然，这种方法严格意义上说是不严谨的。

也可以把每个访问过的节点指向head节点，意义是强行改变指针，也可以改变指针为某一地址，总之，只要能让原先节点变得有标志意义。

注意：

• 换值严格意义上是错误的，但通常可行，我们可以换成一个比较大的数。
• 改变指针的思想是完全可用的。

优劣势分析：

• 这种方法的最大弊端就是改变了原来的链表结构，意义不大，一般只在仅仅为了判断是否成环的时候使用，否则链表结构改变是不可逆的，这个链表将无法使用。
• 时间复杂度：O（N）。
• O（1）。

0x03.解决代码–哈希表

bool hasCycle(ListNode *head) {
   unordered_set<ListNode*> map;
   while(head){
       if(map.count(head)) return true;
       else map.insert(head);
       head=head->next;
   }
   return false;
 }
 

0x04.解决代码–快慢双指针

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

0x05.解决代码–标志法

bool hasCycle(ListNode *head) {
   int flag=1e6;
   while(head){
       if(head->val==flag) return true;
       else head->val=flag;
       head=head->next;
   }
   return false;
}

ATFWUS --Writing By 2020–03–24