判断单链表是否有环？

问题概述

如果存在环就返回true，不存在就false
接下来我提供两种思路

利用hash
快慢指针

方案一：hash法

解题思路

这方法其实相对来说比较容易理解。大致思路就是：
遍历单链表，在遍历的时候，先判断当前节点索引是否在hash表中，如果不存在则将当前节点的索引存入到hash表中，如果当前节点索引已经存在于hash表中，则说明链表又绕回来了，说明链表有环，并且这个节点就是入环节点，直接返回true。

代码实现

完整代码实现：

import java.util.HashMap;
/** * 单向链表类 */
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    // 主方法测试
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        pHead.next = node2; node2.next = node3; node3.next = node4; node4.next = node5;
        node5.next = node3; // 这里成环了
        boolean hasCycle = hashCycle(pHead);
        System.out.println("是否存在环："+hasCycle);
    }

    /** * 方案一 hash法 * @param pHead * @return */
    public static boolean hashCycle(ListNode pHead) {
        ListNode cur = pHead;
        // 创建一个hash表
        HashMap<ListNode, Integer> hash = new HashMap<>();
        while (cur != null) {
            // 如果当前索引不在hash表中 则添加
            if (hash.get(cur) == null) {
                hash.put(cur, 1);
            } else {
                return true;
            }
            // 指针后移
            cur = cur.next;
        }
        // 如果能走出while循环 则说明该链表不存在环
        return false;
    }
}

方案一：快慢指针法

解题思路

该方法是用快慢指针做，时间复杂度可以是O(1),效率很高。
如何用快慢指针来做呢？无非就是判断快慢两个指针最后是否会相遇，如果有环的话，快慢两个指针最后肯定会相遇。
用快慢指针来解决这个问题就好比龟兔赛跑一样，如果赛道是一个环的话兔子和乌龟最终都会相遇，最重要的是一快一慢（一般fast指针走2步，slow指针走1步），以及两个指针的速度最后取合适的值（若fast走其他大于2的步数，则当fast追slow时步数差减少有可能会错过0步，直接超过slow，当环数处于一个特殊值时两个指针可能永远不会相遇，每次将要相遇时fast将会直接超过slow）

代码实现

/** * 单向链表类 */
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    // 主方法测试
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        pHead.next = node2; node2.next = node3; node3.next = node4; node4.next = node5;
        node5.next = node3; // 这里成环了
        boolean hasCycle = hashCycle(pHead);
        System.out.println("是否存在环："+hasCycle);
    }

    /** * 方案一 快慢指针法 * @param pHead * @return */
    public static boolean hashCycle(ListNode pHead) {
        ListNode fast = pHead;  // 快指针
        ListNode slow = pHead;  // 慢指针

        while (fast != null && slow != null) {
            // 快、慢指针后移
            if (fast.next != null) {    // 先判断fast.next是否为null 防止下面那个代码报空指针异常
                fast = fast.next.next;  // 快指针每次循环 有两步
            } else {
                return false;
            }
            slow = slow.next;   // 慢指针每次循环 有一步
            // 如果fast=slow则说明两个指针相遇了 一定存在环
            if (fast == slow) {
                return true;
            }
        }
        // 如果跳出while循环 也说明该链表不存在环
        return false;
    }
}

链表中环的入口结点

问题链接

【JZ23 链表中环的入口结点】

该题相当于是在上个问题的基础上加了一问，不仅要判断是否成环，还要返回成环的第一个节点，即入环节点

其实该题也可以用两种方式去做，hash和双指针。
hash的话，和上面判断是否成环？的代码差不多，不同的是，在返回结果时，直接返回节点索引即可，这里这部分代码我就不演示了，接下来我只讲解双指针这种思路的解法。

解题思路

我先说解题步骤：

首先快、慢指针都从起点开始向前走，快指针-fast每次走2步，慢指针-slow每次走1步
当他们相遇时（判断出有环），记下相遇点
然后快指针-fast从起点开始、慢指针-slow从相遇点开始，都以每次走1步的速度向前走。（其实这里只要保证一个指针从起点走，一个指针从相遇点走就可以了，并不一定非是fast指针从起点走）
当他们再次相遇时，这次的相遇点就是入环点

当然上面只是结论，其实这里是一个数学问题，在他们第一次相遇时，由于快指针-fast的速度是慢指针-slow的两倍，因此快指针走的路程也是慢指针的2倍，因此可以建如下关系式

最后得出结论：a = (m-2n-1)(b+c)+c
也就是fast指针从起点开始走到入环节点的路程，slow指针从相遇点走c的路程+整数圈环 一定刚好到达入环节点

代码实现

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;    // 快指针 每次走两步
        ListNode slow = pHead;    // 慢指针 每次走一步
        boolean hasCycle = false;    // 是否存在环
        
        // 1、先判断是否存在环
        while(fast != null && slow != null) {
            // 1.1、快慢指针后移
            if(fast.next != null) {    // 防止空指针异常
                fast = fast.next.next;    // 每次走两步
            }else {    // 如果fast.next 为null 也证明无环
                return null;
            }
            slow = slow.next;    // 每次走一步
            // 1.2、当快指针等于慢指针时 则说明二者相遇，那么就一定存在环
            if(fast == slow) {
                hasCycle = true;
                break;
            }
        }
        // 2、如果不存在环 就直接返回null
        if(!hasCycle)    // 如果不存在环， 直接返回null
            return null;
        
        // 3、快指针从头结点出发（指针指向pHead）,慢指针从相遇点出发(指针指向不变)
        fast = pHead;
        // 4、新一轮移动 一个指针从头结点 一个指针从相遇节点（哪个从头结点哪个从相遇点都无所谓）
        while(fast != slow) {
            // 快慢指针后移 每轮都走一步
            fast = fast.next;
            slow = slow.next;
        }
        // 5、当快慢指针再次相遇时 就是入环节点
        return fast; // 或者 return slow；
    }
}

判断单链表是否有环？以及入环节点