数据结构与算法 - 实战：判断链表中是否存在环

题目1：判断给定的链表是否存在环

思路：

使用两个具有不同移动速度的指针。如果链表有环，两个指针就会在环中相遇；如果链表没有环，移动快的指针遇到null就结束。

“相遇”其实是一种追赶，移动快的指针会在环中追赶上移动慢的指针；形象一点，可以设想乌龟和兔子在一个环形轨道上赛跑，那么跑得快的兔子就会追赶上乌龟。

设定：指针slowPtr每次移动一个结点，指针fastPtr每次移动两个结点

注意：代码中的ListNode类，参考单链表

/**
 * 判断给定的链表是否包含环
 * @param headNode 链表的头结点
 * @return true：表示链表包含环；false：表示链表不包含环
 */
public static boolean doesLinkedListContainsLoop(ListNode headNode){
    // 首先判断链表是否存在
    if (headNode == null) {
        return false;
    }
    // 初始化slowPtr和fastPtr指针，使其都指向头结点
    ListNode slowPtr = headNode;
    ListNode fastPtr = headNode;
    // slowPtr指针每次移动一个结点;fastPtr每次移动两个结点
    while(slowPtr.getNext() != null && fastPtr.getNext().getNext() != null){
        slowPtr = slowPtr.getNext();
        fastPtr = fastPtr.getNext().getNext();
        if (slowPtr == fastPtr) {
            return true;
        }
    }
    return false;
}

题目2：判断给定的链表是否存在环，如果存在，找到环的起始结点

以下的算法证明，参考自http://www.cnblogs.com/ccdev/archive/2012/09/06/2673618.html

算法描述：

当fastPtr在环内第一次最赶上slowPtr时，slowPtr肯定没有走完链表，而fast已经在环内循环了n圈(1<=n)。
假设slowPtr走了s步，则fastPtr走了2s步（fastPtr的步数还等于s加上在环上多转的n圈），设环长为r，则：

2s= s + nr
s=nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

因为s = a + x 所以有 a + x = nr

a+x = (n–1)r + r = (n-1)r + (L-a)
a=(n-1)r + (L–a–x)

(L–a–x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点距离 = (n-1)圈的环长 + 相遇点到环入口点距离于是我们在链表头和相遇点分别设一个指针，两个指针每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。也就是说，假设使fastPtr指向链表头结点，使slowPtr指向相遇点，两个指针同时移动，每次移动一个结点，当fastPtr移动到环开始的结点时，移动的距离就为a;此时slowPtr就移动了(n-1)圈的环长+相遇点到环入口点的距离两个指针相遇的结点就是环的入口结点。


/**
 * 找到链表中环的开始结点即入环口。
 * @param headNode 链表的头结点
 * @return 环入口结点
 */
public static ListNode findBeginOfLoop(ListNode headNode) {
    // 先判断链表中是否有环
    boolean loopExists = false;
    // 初始化slowPtr和fastPtr指针，使其都指向头结点
    ListNode slowPtr = headNode;
    ListNode fastPtr = headNode;
    while(slowPtr.getNext() != null && fastPtr.getNext().getNext() != null){
        slowPtr = slowPtr.getNext();
        fastPtr = fastPtr.getNext().getNext();
        if (slowPtr == fastPtr) {
            System.out.println("找到环的入口");
            // 链表中环存在
            loopExists = true;
            // 跳出循环，一定要写，不然就是死循环
            break;
        }
    }
    // 如果环存在
    if (loopExists) {
        fastPtr = headNode;
        // slowPtr指针和fastPtr指针每次移动一个结点
        while(slowPtr != fastPtr){
            slowPtr = slowPtr.getNext();
            fastPtr = fastPtr.getNext();
        }
        return slowPtr;
    }
    // 如果不存在
    return null;
}

题目2：判断给定的链表是否存在环，如果存在，返回环的长度；
思路：首先找到slowPtr指针和fastPtr指针两个指针的相遇点，然后保持fastPtr指针不动，使slowPtr指针继续移动，每次移动一个结点。

/**
 * 如果链表中存在环，求环的长度
 * @param headNode 链表的头结点
 * @return 环的长度
 */
public static int getLengthOfLoop(ListNode headNode){
    int length = 0;
    // 先判断链表中是否有环
    boolean loopExists = false;
    // 初始化slowPtr和fastPtr指针，使其都指向头结点
    ListNode slowPtr = headNode;
    ListNode fastPtr = headNode;
    while(slowPtr.getNext() != null && fastPtr.getNext().getNext() != null){
        slowPtr = slowPtr.getNext();
        fastPtr = fastPtr.getNext().getNext();
        if (slowPtr == fastPtr) {
            System.out.println("找到环的入口");
            // 链表中环存在
            loopExists = true;
            // 跳出循环，一定要写，不然就是死循环
            break;
        }
    }
    // 如果环存在
    if (loopExists) {
        do {
            slowPtr = slowPtr.getNext();
            length++;
        } while (slowPtr != fastPtr);
    }
    // 返回环的长度
    return length;
}

05、数据结构与算法 - 实战：判断链表中是否存在环