网站弹窗公告代码,wordpress升级插件出现意外错误,英语外贸网站建设,营销咨询141.环形链表 法一#xff1a;快慢指针
思路#xff1a;
用两个指针slow,fast,后者能比前者多走一步路#xff0c;那判断是不是有环#xff0c;只需要判断是否会相遇。
就是有一个能比乌龟跑2倍快的兔子#xff0c;两小只都在有环的路上跑#xff0c;那是不是肯定会相…141.环形链表 法一快慢指针
思路
用两个指针slow,fast,后者能比前者多走一步路那判断是不是有环只需要判断是否会相遇。
就是有一个能比乌龟跑2倍快的兔子两小只都在有环的路上跑那是不是肯定会相遇。
嗯对
代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//快慢指针参考物理上面的二者是肯定会相遇的这个根本就不用想if(headnull||head.nextnull){return false;}ListNode slowhead;ListNode fasthead.next;while(slow!fast){if(fastnull||fast.nextnull){return false;}slowslow.next;fastfast.next.next;}return true;}
}
法二哈希表
思路
就是把之前走过的路标记一下这里可以用哈希表setset集合中是不允许有重复元素的。然后当重复结点出现的时候,就说明有环了。代码如下
代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {SetListNode seennew HashSetListNode();while(head!null){if(!seen.add(head)){return true;}headhead.next;}return false;}
}
142.环形链表II 这道题可以借鉴141.环形链表的解法不过是用哈希表的没多少改动但是用快慢指针的话那就需要额外注意了。
在这里的话我犯了一个错误用快慢指针法的时候我认为两指针相遇的结点就是该链表开始入环的第一个节点。还有就是当head[-1, -7, 7, -4, 19, 6, -9, -5, -2, -5] ,p9时就错误的认为两个-5就是相同的。
题解
设一个情景方便理解。有个乌龟和兔子兔子腿长当然就跑的比较快这里我规定其速度为乌龟的两倍。它俩在一个有环的地方相遇。看下图红点的地方是相遇点然后我们可以得出乌龟走的路是XY兔子的是XYN*(YZ)这个能看懂吧然后两者的关系是2*(XY)XYN*(YZ)因为速度是2倍关系。然后化简最后就是X(n-1)(YZ)Z。好这里的话。我们这样来理解。当n等于1时XZ意味着只要用个命运之手将爬到相遇点的乌龟放到原点多多少少有点残忍然后再将兔子限速为乌龟的速度这样二者必将会在目的点相遇这个时候我们只需要返回即可。那么当n1时那也没关系这就说明x的确实有点长兔子只需要继续保持着龟速前进即可。图有点丑见谅见谅 代码如下啦
参考官方
码一快慢指针
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(headnull) return null;ListNode slowhead,fasthead;while(fast!null){slowslow.next;if(fast.next!null){fastfast.next.next;}else{return null;}if(fastslow){ListNode ptrhead;while(ptr!slow){ptrptr.next;slowslow.next;}return ptr;}}return null;}
}
码二哈希表
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {SetListNode seennew HashSetListNode();while(head!null){if(!seen.add(head)){return head;}headhead.next;}return null;}
}
其实还挺简单的主要就是要理解
好了刷题快乐哟~
