题解 | #判断链表中是否有环#快慢指针/哈希表

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

解法1: 快慢指针

终止条件：slow/fast是空指针，或者slow==fast

如果终止的时候slow和fast是相等的，那么说明他们在环中相遇了，返回true

如果终止的时候slow或者fast到底了，那么说明他们没有相遇，fast先到的链表尾部

解法2: 哈希表

import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        Set<ListNode> visited = new HashSet<ListNode>();
        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }
}

时间复杂度： O(n)

空间复杂度：O(n)