[数据结构与算法]leetcode 142. 环形链表 II（双指针）

题意

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题思路

① 设双指针 $fast$ 和 $slow$ ，其中$fast$ 每次前进2步、 $slow$每次前进1步。如果$fast$ 最终为NULL，那么该链表无环；反之，$fast$ 和 $slow$必会在某一点相遇。
② 设$fast$ 和 $slow$相遇的点为$P$，那么$slow$从$P$点开始，$fast$从起始点，两个指针同时每次都前进一步，那两者最终相遇的地方即链表入环的第一个节点。

代码

/**
 * 给定一个链表，如果有环路，找出环路的开始点。
 *
 * @author ZhangLingRan
 */

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

/**
 * @author ZhangLingRan
 */
public class Solution{

    public ListNode detectCycle(ListNode head) {

        ListNode fast = head, slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

        // 如果fast走到头，说明没环，那么返回NULL
        if (fast == null || fast.next == null) {
            return null;
        }

        //如果有环，那么找到第一次相遇的交点，slow从交点往后走、fast从head往后走，直到相遇即为交点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

方法证明

假设这是一个带有环的链表；其中$OQ$的长度为$L1$，环的长度为$L2$；两个指针在$P$点相遇，那么当指针$slow$走到了$P$点，其走过的路程为$|OP|=L1+|QP|$，那么$fast$指针走过的路程为$2|OP|=L1+L2+|QP|$。
由此可知：
$$2|OP|=L1+L2+|QP|=2(L1+|QP|)$$
化简得
$$L2?|QP|=L1，即|PQ|=L1$$
其中$|QP|$表示从$Q$点到$P$点走过的路程，$|PQ|$表示从$P$点到$Q$的走过的路程。
由$|PQ|=L1$可知，从$P$点和$O$点同时开始，每次前进一步，相遇点即链表的入环点。

-------------------我是分界线-----------------------
代码更新：

public ListNode detectCycle(ListNode head) {

        ListNode fast = head, slow = head;

        // 如果fast走到头，说明没环，那么返回NULL
        do{
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }while (fast != slow);

        //如果有环，那么找到第一次相遇的交点，slow从交点往后走、fast从head往后走，直到相遇即为交点
        fast = head;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }