秀米h5页面怎么制作,seo技术培训教程视频,山东临沂市需要建设网站的公司,三个字公司名字大全必过环形链表 II
题目
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;…环形链表 II
题目
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。解题思路
利用数组保存遍历过的节点在遍历新节点时判断是否在数组中存在相同的节点。js数组的includes方法判断值相等问题用的是严格相等即指向型引用地址是否相等。
代码1
/*** param {ListNode} head* return {ListNode}*/
var detectCycle function(head) {let arr new Array();//数组中用以存放遍历过的节点let i0;let ph new ListNode(0);//临时指针用以遍历链表ph head;while(1){if(phnull) return null;//如果节点为null则结束循环if(!arr.includes(ph)) arr.push(ph);//如果节点不在数组中则将节点加入数组else {//如果节点在数组中则说明链表循环了return ph;//返回这个循环的节点}ph ph.next;}
};代码2
var detectCycle function(head) {const visited new Set();//将已访问过的节点存入set集合中while (head ! null) {if (visited.has(head)) {//当当前节点存在在set集合中时表明已经访问过此时开始了循环return head;}visited.add(head);head head.next;}return null;
};快慢指针解题思路
我们使用两个指针fast与slow。它们起始都位于链表的头部。随后slow指针每次向后移动一个位置而fast指针向后移动两个位置。如果链表中存在环则fast指针最终将再次与slow指针在环中相遇。
代码
var detectCycle function(head) {let fast null,slownull;fast slow head;while(fast){slow slow.next;//慢指针一次移动一位if(fast.next!null){fast fast.next.next;//快指针一次移动两位}else return null;//当快指针指向节点的第二给节点为null时也返回null//当快慢指针相遇时满指针到入环第一给节点的距离和头节点到入环第一个节点的距离相等if(fast slow){let ptr head;//此时定义一个新指针开始冲头遍历while(ptr ! slow){//同时移动慢指针和头节点指针直到两指针相遇slow slow.next;ptr ptr.next;}return ptr;//两指针相遇返回相遇节点}}return null;
};
