首页 >后端开发 >PHP问题 > 正文

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

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

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的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) {
                return true;
            }
        }
        return false;
    }}

推荐:2021年PHP面试题大汇总(收藏)》《php视频教程

以上就是PHP和Go如何进行环路链表检测的详细内容,更多请关注php中文网其它相关文章!

php中文网最新课程二维码

声明:本文转载于:何晓东的博客,如有侵犯,请联系admin@php.cn删除

  • 相关标签:PHP Go
  • 相关文章

    相关视频


    网友评论

    文明上网理性发言,请遵守 新闻评论服务协议

    我要评论
  • 专题推荐

    作者信息

    醉折花枝作酒筹

    飞花飘絮,霓裳翩翩舞,几多情愫心飞扬。

    最近文章
    css如何设置指定网格的大小和位置388
    css如何定义网格线大小1107
    教你一招搞定css背景图的大小777
    推荐视频教程
  • PHP安全与漏洞PHP安全与漏洞
  • PHP开发基础之字符串篇PHP开发基础之字符串篇
  • PHP开发基础之数据库篇(PDO)PHP开发基础之数据库篇(PDO)
  • 细说PHP(2021版)第二季细说PHP(2021版)第二季
  • 从0开始进入PHP的世界从0开始进入PHP的世界
  • 视频教程分类