题解 | #判断链表中是否有环#

题目描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度的解法么？
输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试
示例1
输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true

题目分析

有环的链表，在遍历时会在环中一直循环，直观地想，可以使用hash法保存出现的结点，在遍历过程时，碰到重复的结点即为有环。

解题思路

方法1：hash法，记录第一次重复的结点
通过使用set或者map来存储已经遍历过的结点，当出现重复的结点时，即为有环。

方法2：快慢指针
通过定义slow和fast指针，slow每走一步，fast走两步，若是有环，则一定会在环的某个结点处相遇（slow == fast），如下图分析。

代码实现

方法1：hash法，记录第一次重复的结点

public boolean hasCycle(ListNode head) {
        // 使用set来记录出现的结点
        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)，需要将链表的所有结点遍历一遍，时间复杂度为O(n)；
空间复杂度：O(n)，需要额外的n空间的hashset来存储结点。

方法2：快慢指针

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)，最多遍历链表的2*(X+Y)个结点，时间复杂度为O(n)；
空间复杂度：O(1)，需要额外两个快慢指针来遍历结点。