PHP和Go如何进行环路链表检测
本篇内容介绍了“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) { return true; } } return false; }}
“PHP和Go如何进行环路链表检测”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
名称栏目:PHP和Go如何进行环路链表检测
转载来于:http://myzitong.com/article/gijpoh.html