141. Linked List Cycle

题目

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

题目大意

判断链表是否有环，不能使用额外的空间。

解题思路

思路：遍历链表，判断链表的next指针的指向 ×
怎么表示呢？
官方：
可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
反思：
没有面向对象的思维，把链表视为一个对象，不用关注其它细节。

代码

public boolean hasCycle(ListNode head) {
        HashSet<ListNode> listNodes = new HashSet<>();
        //链表遍历，判断节点的下一节点是否为空
        if (head != null) {
            while (head.next != null) {
                //判断哈希表中是否包含此节点
                if (listNodes.contains(head)) {
                    return true;
                } else {
                    listNodes.add(head);
                    head=head.next;//这一步，蛮重要
                }
            }
        }
        return false;
    }

优化

判断Hash表中是否包含节点，可以使用 listNodes.add(head)，能直接返回结果。

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