​LeetCode刷题实战141： 环形链表

今天和大家聊的问题叫做 环形链表，我们先来看题面：https://leetcode-cn.com/problems/linked-list-cycle/

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

题意

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。进阶：你能用 O(1)（即，常量）内存解决此问题吗？

样例

解题

用一个hashSet来存储已经遍历过的节点一旦发现某个节点的next节点已经被遍历过，则说明存在环。时间复杂度和空间复杂度均是O(n)，其中n为链表中的节点个数。

public class Solution1 {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> hashSet = new HashSet<>();
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(null != cur.next){
            if(hashSet.contains(cur.next)){
                return true;
            }
            cur = cur.next;
            hashSet.add(cur);
        }
        return false;
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。