141. 环形链表

思路

快慢指针法:

• 快指针在前，每次走2步
• 慢指针在后，每次走1步

判定有环：当快指针遇上慢指针则为有环

为什么快指针每次走2步？

原因：具体走几步可以自己设定，让快指针每次走2步，而慢指针每次走1步，这样的话，误差较小，快指针在一圈就有可能遇上（位置重合）慢指针。

如果步长过大，可能要多圈才能完成两指针的遇上（位置重合）。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */

class Solution {
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function hasCycle($head) {
        $p1 = $head;
        $p2 = $head;

        while($p1->next != null && $p2->next != null) {
            $p1 = $p1->next;
            $p2 = $p2->next->next;
            if($p1 == $p2) {
                return true;
            }
        }

        return false;
    }
}

系列题

142. 环形链表 II

思路

判断环形链表入口

1. 利用快慢指针判断是否存在环，快指针走两步，慢指针走一步，两者若能相遇，则存在环;
2. 快慢指针相遇后，快指针改为走一步；另取一辅助指针，从头开始也是每次走一步；两者相遇的节点，便是环形链表入口。

为什么快指针和辅助指针相遇，则为环形链表入口？

见官方题解环形链表 II方法二的数学推论；

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast, low, p := head, head, head

    // 利用相遇判断环
    for {
        // 若不存在环，返回nil
        if fast == nil || fast.Next == nil {
            return nil
        }

        // 移动
        fast = fast.Next.Next
        low = low.Next

        // 相遇
        if fast == low {
            break
        }
    }

    // 相遇后，fast 改为每次走一步； p 从链表开头每次走一步；两者相遇的节点，则是环形链表入口；
    for p != fast {
        p = p.Next
        fast = fast.Next
    }

    return p
}