PHP和Go如何进行环路链表检测

链表中环的入口结点问题是一个超级经典的问题，不管是在面试中，还是考研的过程中都是一个经典问题。通常的公认解法就是双指针(快慢指针)的解法，当然这已经的老生长谈的了。今天我们就来介绍介绍。

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

解题思路 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) {                 retu活动：慈云数据爆款香港服务器，CTG+CN2高速带宽、快速稳定、平均延迟10+ms 速度快，免备案，每月仅需19元！！ 点击查看rn true;             }         }         return false;     }}

推荐：

《2021年PHP面试题大汇总（收藏）》《php视频教程》

本文来源网站：info110.com，若侵权，请联系删除。

《PHP和Go如何进行环路链表检测》来自互联网同行内容，若有侵权，请联系我们删除！