判断单向链表是否为环形链表-基于Go

判断单向链表是否为环形链表-基于Go,第1张

概述给定一个链表,判断链表中是否有环。如果链表中存在某个节点,可以通过连续跟踪next指针再次到达该节点,则链表中存在环。如果链表中存在环,则返回true,否则返回false。直接遍历链表,使用set做标记位(标记是否已经到达过)packagemainimport( "fmt")typeNodestruct{ valint

给定一个链表,判断链表中是否有环。
如果链表中存在某个节点,可以通过连续跟踪next指针再次到达该节点,则链表中存在环。
如果链表中存在环,则返回true,否则返回false。

直接遍历链表,使用set做标记位(标记是否已经到达过)
package mainimport (	"fmt")type Node struct{	val int	next *Node}type voID struct{}func hasCycle(head *Node)bool{	set := map[Node]voID{}	for head!=nil{		_, ok := set[*head]		if ok{			// 已经存在了一个相同的Node			return true		}		// 此Node在set中不存在		set[*head] = voID{}		head = head.next	}	return false}func main(){	node5 := Node{5, nil}	node4 := Node{4, &node5}	node3 := Node{3, &node4}	node2 := Node{2, &node3}	node1 := Node{1, &node2}	node5.next = &node3	fmt.Println(hasCycle(&node1))}
使用双指针
func hasCycle2(head *Node)bool{	if head==nil||head.next==nil{		return false	}	slow := head	quick := head.next	for slow!=quick{		if quick==nil||quick.next==nil{			return false		}		slow = slow.next		quick = quick.next.next	}	return true}
总结

以上是内存溢出为你收集整理的判断单向链表是否为环形链表-基于Go全部内容,希望文章能够帮你解决判断单向链表是否为环形链表-基于Go所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1241501.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-06
下一篇 2022-06-06

发表评论

登录后才能评论

评论列表(0条)

保存