141. 环形链表

题意：

解题思路：

思路：
1. 快慢指针思想：如果有环，快指针必定会追上慢指针；
2. hash：存储每一个节点，如果遍历到后面存在相同值，则判断为环，如果能走到最后，直到为空，则判断无环；

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 Boolean
     */
    function hasCycle($head) {
        $fast = $head;
        $slow = $head;
        while ($fast != null && $fast->next != null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
            if ($slow == $fast) {
                return true;
            }
        }
        return false;
    }
    function hasCycleHash($head) {
        $hash = [];
        while ($head) {
            if (in_array($head, $hash)) return true;
            $hash[] = $head;
            $head = $head->next;
        }
        return false;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    hasCycleHash(head)
    if head == nil {
        return false
    }
    slow, fast := head, head.Next
    for slow != nil && fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}
func hasCycleHash(head *ListNode) bool {
    hash := make(map[*ListNode] int)
    for head != nil {
        if _,ok := hash[head]; ok {
            return true
        }
        hash[head] = head.Val
        head = head.Next
    }
    return false
}