LeetCode《初级算法》链表之环型链表 -- JavaScript
题解
1、借助 Set 记录节点是否出现过
判断链表是否存在环，当然最简单的办法就是借助辅助空间，遍历链表，并不断把节点存在辅助空间中，当遍历时出现了相同的节点时，就说明有环；
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { let set = new Set(); // add,delete,.size while(head !== null) { if(set.has(head)) { return true; }else { set.add(head); head = head.next; } } return false; }; 复制代码
2、快慢指针
一个走的快，一个走的慢；
如果有环，则两个指针一定会在某个时刻碰上；
如果没有环，则两个指针一定是一前一后；
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { let quick = head, slow = head; // 把快慢指针的速度设置为 1:2 while(quick !== null && quick.next !== null) { quick = quick.next.next; slow = slow.next; if(slow === quick) { return true; } } return false; }; 复制代码
3、逐个将每个节点的 next 指向自身
这种方法并不好，因为这种方法会改变链表的结构；以下是此方法的具体描述：
循环遍历节点，逐个将每个节点的 next 指向自身；
当链表没有环时，退出出循环；
当链表有环时，会回到环在链表上的起始节点，此时此节点的next指向其本身，退出循环；
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { let temp = head; while(head !== null) { if(head === head.next) { return true; } head = head.next; temp.next = temp; temp = head; } return false; }; 复制代码
大家如果有更好的思路和解法，欢迎大家一起来讨论啊~
这是使用 JavaScript 对 LeetCode《初级算法》的每道题的总结和实现的其中一篇，汇总篇在这里：
作者：火锅国大侠
链接：https://juejin.cn/post/7015150207671222309