题目链接

141. 环形链表

题目描述

给定一个链表，判断链表中是否有环。

如果链表中存在环，则返回 true 。 否则，返回 false 。

解题思路

1. 哈希表

将链表节点不断添加到哈希表中，在添加过程中如果某个节点已经存在于哈希表中，说明链表有环，因为同一个对象地址相同。

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

复杂度分析：

• 时间复杂度：，N 取决于链表的节点个数。
• 空间复杂度：，哈希表需要的额外空间。

  2. 双指针

设置 fast 指针每次前进两步，slow 指针每次前进一步，如果链表有环，两指针一定会相遇。

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

复杂度分析：

• 时间复杂度：，N 取决于链表节点个数。
• 空间复杂度：