牛客例题一百遍：判断链表中是否有环

判断链表中是否有环

• • 描述
  • • 示例1
    • 示例2
    • 示例3
  • 解体思路
  • • 思路一
    • 思路二

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

你能给出空间复杂度O(1)的解法么？

输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

示例1

输入：{3,2,0,-4},1
返回值：true
说明：
第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true 
           

示例2

输入：{1},-1
返回值：false
说明：
第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
           

示例3

输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：true
           

解体思路

思路一

hash法，用hash表当，hash表中有重复的元素时，则为有环，代码如下:

public boolean hasCycle(ListNode head) {
       HashSet<ListNode> set = new HashSet<>();
        while(head != null){
           // 当set中包含结点，说明第一次出现重复的结点，即环的入口结点
            if(set.contains(head)){
                return true;
            }
            // set中加入未重复的结点
            set.add(head);
            head = head.next;
        }
        return false;
    }
           

复杂度分析：

时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。

空间复杂度：O(N)，需要数组保存数据。

思路二

快慢指针法，当快慢指针相遇，使即有环，否则无环，则代码如下：

public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        // 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            // 快指针是满指针的两倍速度
            fast = fast.next.next;
            slow = slow.next;
            // 记录快慢指针第一次相遇的结点
            if(slow == fast) return true;
        }
        return false;
    }
           

复杂度分析：

时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)，无需额外的空间。