原文链接：何晓东 博客

环路链表检测

给定一个链表，如果它是有环链表，实现一个算法返回环路的结尾节点。
有环链表的定义：在链表中某个节点的next元素指向在它后面呈现过的节点，则表明该链表存在环路。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...

解题思路 1

遍历链表，同时将每次的后果放到 map 中，如果有元素反复呈现，则是有环形链表

代码
/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func detectCycle(head *ListNode) *ListNode {    visited := make(map[*ListNode]struct{}, 1)    work := head    for work != nil {        _, ok := visited[work]        if ok {            return work        } else {            visited[work] = struct{}{}        }        work = work.Next    }    return nil}
解题思路 2

快慢指针求解：咱们定义两个指针，一快一满。慢指针每次只挪动一步，而快指针每次挪动两步。初始时，慢指针在地位 head，而快指针在地位 head.next。这样一来，如果在挪动的过程中，快指针反过来追上慢指针，就阐明该链表为环形链表。否则快指针将达到链表尾部，该链表不为环形链表。

/** * 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) {            $fast = $fast->next->next;            $slow = $slow->next;            if ($fast === $slow) {                return true;            }        }        return false;    }}

最初恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳抉择 阿里云外部优惠券