单链表之判断表中是否存在环

这篇依然是学习专栏《数据结构与算法之美》的拓展练习。
链表中的环其实是一个挺有趣的问题，如果链表中存在环，对其进行遍历的时候就会发现next永远存在节点，循环往复永远不会终止。所以我们在遍历链表之前还是判断链表中是否存在环安全一点。

这篇文章不止讲解了如何判断链表中是否存在环，还贴出了链表中非环部分的长度、环的长度、环的起始点这些算法。

判断链表中是否存在环

方法一：使用快慢节点

思路

学习过其他链表算法的同学应该对快慢指针方法很熟悉了，这里也是使用快慢指针的方法。

原理就是，快指针既然走的比慢指针快，那么当链表中存在环的时候，快慢指针必定在一个位置会相遇，也就是pFast=pSlow。当这个条件一成立我们即可以断定这个链表存在环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * 使用快慢指针，
     * 快指针每次走两步，慢指针每次走一步
     * 如果链表中有环，那两个指针必定有相遇的时候
     * @param head
     * @return
     */
    public static boolean doesLinkedListHasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode pFast = head.next.next,pSlow = head.next;

        while (pFast.next != null && pSlow.next != null) {
            if (pFast == pSlow) {
                return true;
            }
            pFast = pFast.next.next;
            pSlow = pSlow.next;
        }
        return false;
    }

方法二：使用Map将节点作为key

思路

这里就是利用的Map的key唯一的特性，遍历链表，当发现map中已经存在当前遍历到的节点时，即我们是再一次来到了这个节点，证明链表存在环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 使用Map将每一个走过的节点存进去
 * 在存之前get一下，如果get有值，说明之前存过，即证明有环
 * @param head
 * @return
 */
public static boolean doesLinkedListHasCycle1(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    final HashMap<ListNode, Object> map = new HashMap<>();
    ListNode p = head;

    while (p.next != null) {
        if (map.containsKey(p)) {
            return true;
        }
        map.put(p, null);
        p = p.next;
    }

    return false;
}

查找环的起点

思路

查找环的起点的前提就是链表要存在环，所以此算法的前半部分就是利用了前面的快慢指针判断法，不同的是，当确定存在环的时候我们即跳出循环。

这里有一个推导过程，我参考别人的博客。

推导过程
推导过程

参考：https://blog.csdn.net/jiaobuchong/article/details/84727007

代码

看懂了上面的推导过程，我们直接按照其实现对应的代码就可以了。

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
/**
 * 查找链表环的起点
 * @param head
 * @return null代表没有环
 */
public static ListNode findCycleHead(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }

    ListNode pFast = head, pSlow = head;
    // 循环直到快慢指针相遇
    while (true) {
        pFast = pFast.next.next;
        pSlow = pSlow.next;
        if (pFast == null) {
            return null;
        }

        if(pFast == pSlow) {
            break;
        }
    }

    // 让快指针等于头节点，然后各自以1 的步长继续前进，直到再次相遇
    // 相遇点即为环的起始点
    pFast = head;
    // 可以顺便计算出非环部分的长度
    int i = 0;
    while (true) {
        pFast = pFast.next;
        pSlow = pSlow.next;
        i++;
        if (pFast == pSlow) {
            System.out.println("length of not cycle in this LinkedList: " + i);
            return pFast;
        }
    }
}

计算环的长度

思路

这个算法依然用到了快慢指针，类比到生活中就像是两个人在操场跑步，一个人跑的快一个人跑的慢一点。

我们现在假设快指针叫快男，慢指针叫慢哥

在计算环长度这个算法中，快男和慢男同时在起点起跑，当快男第一次追上慢哥时（即快男已经领先一圈，假设这里时位置a），这是慢哥停下站在原地不动，快男继续跑，当快男再一次追上慢哥的时候（快男转了一圈回到位置a），所以刚刚快男走过的长度就是环的长度。类比到代码里应该就很好理解了。

要注意的是极端条件的处理，防止异常情况的发生，让代码尽可能的健壮

代码

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
/**
 * 计算环的长度，没有环就返回0
 * @param head
 * @return
 */
public static int calculateCycleLength(ListNode head) {
    if (head == null || head.next == null) {
        return 0;
    }
    ListNode pFast = head, pSlow = head;
    // 直到相遇
    while (true) {
        pFast = pFast.next.next;
        pSlow = pSlow.next;
        if (pFast == null) {
            return 0;
        }
        if (pFast == pSlow) {
            break;
        }
    }

    // pFast停下，pSlow继续走，直到再次相遇 pSlow走过的长度即为环的长度
    int cycleLength = 0;
    while (true) {
        pSlow = pSlow.next;
        cycleLength++;
        if (pSlow == pFast) {
            break;
        }
    }

    return cycleLength;
}