【日拱一卒】链表——判断链表是否有环资料

本文主要介绍【日拱一卒】链表——判断链表是否有环资料 方法和在新技术下所面对的“挑战”,方便大家深入理解【日拱一卒】链表——判断链表是否有环资料 过程。本文也将分享【日拱一卒】链表——判断链表是否有环资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

如何判断一个链表是否有环

需求

判定一个链表是否有环

【日拱一卒】链表——判断链表是否有环

这张图不存在环,头结点是1,尾结点是5。

【日拱一卒】链表——判断链表是否有环

这张图中,节点2-3-4-5-2就构成了环。

 

思路

思路1 ——快慢指针

顾名思义,一个快指针,一个慢指针。

如果不包括环,快慢指针同向行驶,根据小学经典数学题,他们永远无法相遇,而且差距只会越来越大。

如果链表有环,意味着快慢指针都会调头,好比操场跑步,第一圈快指针在慢指针前面,但是后面快指针迟早会追上慢指针。所以可以借助这个思想,使用快慢指针判定是否有环。

【日拱一卒】链表——判断链表是否有环

图中,slow代表慢指针,每次只走一步,fast代表快指针,每次走两步。

第一次:slow停在节点2,fast停在节点3

第二次:slow停在节点3,fast停在节点5

第三次:slow停在节点4,fast停在节点3

第四次:slow停在节点5,fas停在节点5

至此,快指针已经”撵上“了慢指针。

 

代码实现

func hasCycle(head *ListNode) bool { 	slow := head 	fast := head  	for fast.Next != nil && fast != nil { 		if slow.Val == fast.Val { 			return true 		} else { 			slow = slow.Next 			fast = fast.Next.Next 		} 	}  	return false } 

  

思路2——另辟蹊径

遍历链表,如果节点的值与一个特殊的值不相等,则将遍历过的节点的值设置成一个特殊的值,相当于打标记。

如果链表遍历完,发现所有节点都不等于这个特殊的值,则判定链表无环。

如果在遍历的过程中,发现有节点等于这个特殊的值,则认为有环。

 

代码实现

func hasCycle2(head *ListNode02) bool {     if head == nil {       return false     }      for head != nil {       if head.Val == 5201314 {         return true       }        head.Val = 5201314       head = head.Next     }      return false   }

只能说,第一个想到这个思路的,脑洞是有多大~

 

不忘初心

老王:你不好好种地,你以后长大能干什么

小王:学算法

老王:学算法?!你数组、链表、栈、队列、堆、排序、查找都整不明白,你学什么算法

小王:我只学如何判断链表是否有环

老王:。。。

 

如果您觉得阅读本文对您有帮助,请点一下“推荐”按钮,您的“推荐”将是我最大的写作动力!如果您想持续
【日拱一卒】链表——判断链表是否有环资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 【日拱一卒】链表——判断链表是否有环资料

提供最优质的资源集合

立即查看 了解详情