文章目录
  1. 1. 求环入口
    1. 1.1. 思路
    2. 1.2. 代码实现

【题目】:Given a linked list, determine if it has a cycle in it.

使用指针追赶的方法,设定两个指针fast、slow,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。Java代码如下:

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null)
        return false;

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

    return false;
}

求环入口

【题目】:Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

思路

如上图,h是链表起始点,s是环入口,p是两个指针碰撞点。r表示环的长度,r = x+y.

可以证明, a = y + mr (头指针 到 环入口的距离 = 碰撞点p 到 环入口的距离 + 循环多次环 )。证明如下:

当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则: 2s = s + nr s= nr 设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。

s = nr
a + x = nr
a + x = (n1)r +r = (n-1)r + r 
a = (n-1)r + r - x
a = (n-1)r + y

由此可知,从链表头到环入口点等于(n-1)循环内环+ 相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。

代码实现

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

    if (fast.next == null || fast.next.next == null) {
        return null;
    }

    slow = head;
    while (fast.next != null) {
        if (fast == slow)
            return fast;
        fast = fast.next;
        slow = slow.next;
    }
    return null;
}
文章目录
  1. 1. 求环入口
    1. 1.1. 思路
    2. 1.2. 代码实现