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

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

遍历链表，同时将每次的结果放到 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}

快慢指针求解：我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 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;
    }}

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

以上就是PHP和Go如何进行环路链表检测的详细内容！

查看更多关于PHP和Go如何进行环路链表检测的详细内容...