142. 环形链表 II

题意：

解题思路：

思路：快慢指针
1. 快慢指针指向头结点，快指针走两步，慢指针走一步，直到相遇，证明有环；
2. 重新定义快指针指向头节点，两者同时走一步，直到相遇则是环的第一个节点；

PHP代码实现：

/**
 * 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 ListNode
     */
    function detectCycle($head) {
        //hash存储
        $hash = [];
        $node = $head;
        while ($node != null) {
            if(in_array($node, $hash)){
                return $node;
            }
            $hash[] = $node;
            $node = $node->next;
        }
        return false;
    }
    function detectCycleFastSlow($head) {
        $fast = $head;
        $slow = $head;
        while (true) {
            if ($fast === null || $fast->next === null) return null;
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                break;
            }
        }
        $fast = $head;
        while ($fast !== $slow) {
            $fast= $fast->next;
            $slow = $slow->next;
        }
        return $fast;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    cur := head
    fast, slow := cur, cur
    isCircle := false
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            isCircle = true
            break
        }
    }
    if isCircle {
        slow = cur
        for fast != slow {
            fast = fast.Next
            slow = slow.Next
        }
        return slow
    }
    return nil
}