给你一个链表的头节点 head ,判断链表中是否有环。

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

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

    示例 1:
    image.png
    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。

    示例 2:
    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。

    示例 3:
    输入:head = [1], pos = -1
    输出:false
    解释:链表中没有环。

    常规算法:
    使用哈希表来存储访问过的结点,每访问一个结点,先判断哈希表中是否已存在该结点,若存在,则表示有环,反之直至遍历结束

    1. public boolean hasCycle(ListNode head) {
    2. Set<ListNode> nodeSet = new HashSet<>();
    3. while (head != null) {
    4. if(nodeSet.contains(head)) {
    5. return true;
    6. }
    7. nodeSet.add(head);
    8. head = head.next;
    9. }
    10. return false;
    11. }

    该算法可以稍微优化一下:若哈希表 add 未返回 true 则表示哈希表中已经存在该元素

    1. public boolean hasCycle(ListNode head) {
    2. Set<ListNode> nodeSet = new HashSet<>();
    3. while (head != null) {
    4. if(!nodeSet.add(head)) {
    5. return true;
    6. }
    7. head = head.next;
    8. }
    9. return false;
    10. }

    该算法借用容器存储访问过的结点,空间复杂度 O(n)

    还有一种借助快慢指针的双指针算法,无需借用容器存储结点,只需借助两个指针即可:
    一个快指针 fast,一个慢指针 slow
    慢指针 slow 前进一步,快指针 fast 就前进两步
    如果 fast 最终遇到空指针,说明链表中没有环
    如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环
    类似于跑圈中跑的慢的被跑的快的套圈了

    image.png

    1. /**
    2. * 双指针-快慢指针
    3. *
    4. * @param head
    5. * @return
    6. */
    7. public boolean hasCycle(ListNode head) {
    8. // 快慢指针都指向头结点
    9. ListNode fast = head;
    10. ListNode slow = head;
    11. // 快指针走到末尾时停止
    12. while(fast != null && fast.next != null) {
    13. // 慢指针走一步,快指针走两步
    14. slow = slow.next;
    15. fast = fast.next.next;
    16. // 快慢指针相遇,说明有环
    17. if (slow == fast) {
    18. return true;
    19. }
    20. }
    21. // 没有环
    22. return false;
    23. }