中宁网站建设公司,北京网站开发飞沐,图们网络推广,常州天宁区建设局网站目录
1,题目
2#xff0c;代码
2.1快慢指针
2.2#xff0c;哈希表
3#xff0c;学习与总结
3.1自己尝试写快慢指针 反思 1,题目
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达代码
2.1快慢指针
2.2哈希表
3学习与总结
3.1自己尝试写快慢指针 反思 1,题目
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 2代码
2.1快慢指针
/*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*//*** param {ListNode} head* return {boolean}*/
var hasCycle function(head) {if (head null || head.next null) {return false;}let slow head;let fast head.next;while (slow ! fast) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;};
2.2哈希表
哈希表中存储的是 每个节点的引用地址通过判定引用地址是否再次被指向判定是否有环形链表的存在
/*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*//*** param {ListNode} head* return {boolean}*/
var hasCycle function(head) {const hashtable new Set()while(head ! null){if(hashtable.has(head)){return true}hashtable.add(head);head head.next;}return false;};
3学习与总结
3.1自己尝试写快慢指针 反思 1为什么比较‘slow ! fast’而不是‘slow.val ! fast.val’ 我们在判断链表是否有环时关注的是节点的引用或内存地址是否相同而不仅仅是节点值是否相等
节点引用内存地址比较
slow !fast 确保我们检查的两个指针是否指向链表的同一个节点
节点值比较
slow.val ! fast.val比较节点值是否相等 在环形链表的场景下slow 和 fast 指针最终会指向同一个节点这不仅仅意味着它们的值相等而是它们确实指向同一个物理位置或内存地址。这是检测链表中环存在的可靠方法。 2为什么是要是‘ if (fast null || fast.next null) ’ 作用用于在追踪链表中的可能环形结构时算法的安全性和准确性
终止条件的检测在非环形链表中末尾节点的next属性是null。因此 fast null 检查是为了判断快指针是否已经超出了链表的最末端即快指针已经没有指向任何节点。fast.next null 检查是为了判断快指针的下一个步骤是否会超出链表的最末端。因为快指针每次移动两步如果快指针的下一步就是链表的末端那么它就没有下一个“next”节点可以进一步移动到这也表明链表中不存在环。 预防空指针异常在许多编程语言中尝试访问null的属性或方法会导致空指针异常在JavaScript中称为TypeError。
算法的正确性如果链表中存在环快慢指针最终会在环内的某个位置相遇而如果快指针达到了链表的末尾fast null 或 fast.next null这意味着链表不可能有环。 快指针移动速度在算法中快指针fast每次移动两步而慢指针slow每次移动一步。如果链表中存在环快指针最终会追上慢指针因为它们会在环内的某个点相遇。但如果链表中没有环快指针会先达到链表的末尾。
