双指针普通指针：两个指针同向或不同方向碰撞指针：两个指针靠得更近快慢指针：一个一快一慢）给你一个链表的头节点head，判断链表是否有环。如果链表中有一个结点可以通过不断跟踪next指针再次到达，那么链表中就存在环路。为了表示给定链表中的环，评估系统内部使用整数pos表示链表尾部相连的链表中的位置（索引从0开始）。注意：pos不作为参数传递。只是为了识别链表的实际情况。如果链表中存在循环，则返回true。否则，返回false。示例1：输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个环，其尾部连接到第二个节点。示例2：输入：head=[1,2],pos=0输出：true解释：链表中有一个环，其尾部连接到第一个节点。示例3：输入：head=[1],pos=-1输出：false解释：链表中没有循环。提示：链表中节点个数的范围是[0,104]-105<=Node.val<=105。pos为-1或链表中的有效索引。更进一步：你能用O(1)（即常量）内存解决这个问题吗？方法一、哈希表或集合：动画太大，点击查看思路：准备一张图或集合，然后循环链表。每遍历一个节点，判断当前节点是否存在于地图中，如果不存在，则将当前节点添加到地图中。如果存在，则说明这个节点之前被访问过，也就是说这个链表是有环的。复杂度分析：时间复杂度O(n)，n是链表的个数，最坏情况下，每个节点都要遍历。空间复杂度O(n)，n是一个map或者setjs，存储遍历的节点：varhasCycle=(head)=>{letmap=newMap();while(head){if(map.has(head))returntrue;//如果当前节点存在于map中，则说明存在循环map.set(head,true);//否则加入maphead=head.next;//迭代节点}returnfalse;//循环完成如果没有重复的节点，则表示没有循环};方法二、快慢指针动画过大，点击查看思路：准备两个快慢指针，循环链表，慢指针一开始也指向头部，每循环向前走一步，快的指针初始指向头部，每循环向前移动两步。如果没有环，则快指针到达终点。如果有环，快指针就会追上慢指针。复杂度：时间复杂度O(n)，空间复杂度O(1)js:varhasCycle=function(head){//设置快慢指针letslow=head;让快=头；//如果没有循环，fast指针会到达终点，否则继续移动双指针while(fast&&fast.next){slow=slow.next;fast=fast.next.next;//快慢指针相遇，说明存在循环if(slow==fast){returntrue;}}返回假；}；142.环链表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输出：returnnull解释：链表中没有循环。提示：链表的节点数在[0,104]-105<=Node.val<=105pos的值为-1或链表中的有效索引进阶：可以使用O(1)空间解决这个问题？方法一、哈希表思想：遍历链表，将节点添加到一个集合中，每次判断当前节点是否在集合中。如果有重复节点，则该节点为入口节点。复杂度：时间复杂度O(n)，空间复杂度O(n)js:vardetectCycle=function(head){constvisited=newSet();while(head!==null){//终止条件，如果没有循环，则跳出循环if(visited.has(head)){//如果有重复节点，则此节点为入口返回头；}visited.add(head);//将节点添加到集合中head=head.next;}返回null;};方法二、快慢指针动画过大，点击查看思路：慢指针移动两步，快指针移动一步，相遇后快指针变成头指针，然后每次快慢指针走一步直到相遇，相遇的节点为入口链接点复杂度：时间复杂度O(n)，空间复杂度O(1)js:vardetectCycle=function(head){if(head===空）{返回空；}让慢=头，快=头；while(fast!==null){slow=slow.next;//慢指针移动两步，快指针移动一步if(fast.next!==null){fast=fast.next.next;}else{returnnull;//如果没有ring,returnnull}if(fast===slow){//有ringletfast=head;//fast指针指向头节点，然后fast和slow指针每走一步直到相遇，相遇的节点为入口节点while(fast!==slow){fast=fast.next;慢=慢.next;}快速返回；}}返回null;};15.三数之和（medium）给你一个整数数组nums，判断是否存在满足i!=j,i!=k的三元组[nums[i],nums[j],nums[k]]j!=k，同时满足nums[i]+nums[j]+nums[k]==0请返回所有和为0且不重复的三元组。注意：答案中不允许出现重复的三胞胎。示例1：输入：nums=[-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解释：nums[0]+nums[1]+nums[2]=(-1)+0+1=0。数[1]+数[2]+数[4]=0+1+(-1)=0。数[0]+数[3]+数[4]=(-1)+2+(-1)=0。不同的三元组是[-1,0,1]和[-1,-1,2]。请注意，输出的顺序和三元组的顺序并不重要。示例2：输入：nums=[0,1,1]输出：[]解释：唯一可能的三重和不为0。示例3：输入：nums=[0,0,0]输出：[[0,0,0]]解释：唯一可能的三重和为0。提示：3<=nums.length<=3000-105<=nums[i]<=105方法1.暴力解，对于三个数，循环3次，分别求和，时间复杂度O(n^3)方法2.c=-(a+b)：确定a和b后，可以认为两个数的和相同，求-(a+b)在map中，减少一层循环，时间复杂度O(n^2)，空间复杂度O(n)。方法三、排序后发现动画过大，点击查看思路：先对数组排序，数组长度必须大于3，循环数组，如果当前循环到第i个索引，定义两个指针L=i+1，R=nums。length-1，如果sum=nums[i]+nums[L]+nums[R]小于0，则将左指针右移，如果sum大于0，则将右指针移至左边，如果和等于0，正好找到这3个数，然后试L++，R--，继续找中间三个数的和是否等于0。注意，在循环过程中需要删除相同的三个数字。复杂度分析：时间复杂度O(n^2)，n为数组长度。空间复杂度O(logn)，也就是排序需要的空间js:varthreeSum=function(nums){letans=[];constlen=nums.length;if(nums==null||len<3)returnans;//数组长度大于3nums.sort((a,b)=>a-b);//排序(leti=0;i
