2019-08-15：谈一谈如何判断一个链表成环？

[MoJieBlog]

No description provided.

[xingxingxiaoyu]

步长分别为1,2遍历队列，如果.next为空就无环，否则两个遍历一定会到同一个节点，也就是有环

[gabyallen]

将所有的遍历过的节点用某个结构存储起来，然后每遍历一个节点，都在这个结构中查找是否遍历过，如果找到有重复，则说明该链表存在循环；如果直到遍历结束，则说明链表不存在循环。

[zzhuazi]

用HashMap存储next指向的地址，若map中存在，则有环，否则无环。

[luckyAF]

一个指针A每次走一步，一个指针B每次走二步，假如有环，那么指针B一直比指针A快，一定会有套圈的一刻存在，即指针A和指针B重叠。没有环的话，就是直到指针B指向null，两个指针还没遇上。

[zhizhulp]

题目不严谨，应该是如何判断一个单链表成环。

[MoJieBlog]

题目不严谨，应该是如何判断一个单链表成环。

莫非单聊表和双链表成环你有不同的判断方法？

[siwenyang]

Two ways to solve:

/////////////Two Pointers: /////////////////////////

public boolean hasCycle(ListNode head) {
    if(head==null || head.next==null){
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while(slow != fast){
        if(fast==null || fast.next==null)
            return false;
        fast=fast.next.next;
        slow=slow.next;
    }
    return true; 
}

/////////////HashSet:///////////////////////////

public boolean hasCycle(ListNode head) {
    Set<ListNode> dict = new HashSet<>();
    
    while(head != null){
        if(dict.contains(head)){
            return true;
        } else {
            dict.add(head);
        }
        head = head.next;
    }
    return false;
}

[Zander2014]

Two ways to solve:

/////////////Two Pointers: /////////////////////////

public boolean hasCycle(ListNode head) {
    if(head==null || head.next==null){
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while(slow != fast){
        if(fast==null || fast.next==null)
            return false;
        fast=fast.next.next;
        slow=slow.next;
    }
    return true; 
}

/////////////HashSet:///////////////////////////

public boolean hasCycle(ListNode head) {
    Set<ListNode> dict = new HashSet<>();
    
    while(head != null){
        if(dict.contains(head)){
            return true;
        } else {
            dict.add(head);
        }
        head = head.next;
    }
    return false;
}

HashSet的方法可以精简一下，add方法本身会返回true/false，true代表添加成功，false代表已经包含，添加失败