PHP 和 Go 实现环路链表检测

码农天地 -
PHP 和 Go 实现环路链表检测

原文链接:何晓东 博客

环路链表检测

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

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

特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。

php介绍

PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。

Tags 标签

链表leetcodephpgolang

扩展阅读

加个好友,技术交流

1628738909466805.jpg