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

判断单链表是否有环？

问题概述

如果存在环就返回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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

方案一：快慢指针法

解题思路

该方法是用快慢指针做，时间复杂度可以是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) {
    	if(pHead == null) return false;
    	if(pHead.next == null) return false;
        ListNode slow = pHead.next;  // 慢指针，一次走一步
        ListNode fast = pHead.next.next;  // 快指针，一次走两步
        while (slow != fast) {
        	if(fast == null || fast.next == null) {
				return false;
			}
            slow = slow.next;   // 慢指针，一次走一步
            fast = fast.next.next;	// 快指针，一次走两步
        }
        // 如果跳出while循环 ，说明fast与slow相遇了， 也说明该链表存在环
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

链表中环的入口结点

问题链接

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

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

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

解题思路

我先说解题步骤：

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

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

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

代码实现

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    	if(pHead == null) return null;
    	if(pHead.next == null) return null;
        ListNode slow = pHead.next;  // 慢指针，一次走一步
        ListNode fast = pHead.next.next;  // 快指针，一次走两步
        while (slow != fast) {
        	// 如果不存在环 就直接返回null
        	if(fast == null || fast.next == null) {
				return null;
			}
            slow = slow.next;   // 慢指针，一次走一步
            fast = fast.next.next;	// 快指针，一次走两步
        }
        // 快指针 或者 慢指针 从头结点出发（指针指向pHead）,慢指针从相遇点出发(指针指向不变)
        slow = pHead;
        // 新一轮移动 一个指针从头结点 一个指针从相遇节点（哪个从头结点哪个从相遇点都无所谓）
        while(fast != slow) {
            // 快慢指针后移 每轮都走一步
            fast = fast.next;
            slow = slow.next;
        }
        // 当快慢指针再次相遇时 就是入环节点
        return fast; // 或者 return slow；
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27