论坛网站制作教程,wordpress登录跳转,怎么做弹幕网站,餐饮网站开发性能需求分析力扣题目#xff1a;环形链表及环形链表II
开篇 今天是备战蓝桥杯的第26天和算法村开营第4天。挑选了链表的黄金关卡与大家分享。
题目一#xff1a;环形链表
题目链接: 141.环形链表
题目描述
方法一、哈希表
判断是否有环#xff0c;可以利用哈希表#xff0c;遍历… 力扣题目环形链表及环形链表II
开篇 今天是备战蓝桥杯的第26天和算法村开营第4天。挑选了链表的黄金关卡与大家分享。
题目一环形链表
题目链接: 141.环形链表
题目描述
方法一、哈希表
判断是否有环可以利用哈希表遍历的时候把节点放进去。当有节点在哈希表出现过时证明存在环
public ListNode detectCycle(ListNode head){
ListNode pos head;
SetListNodevisited new HashSet();
while (pos ! null){if (visited.contains(pos)) return pos;else visited.add(pos);pos pos.next;
}
return null;
}方法二、快慢指针
如果只用O(1)的空间有没有其他方法快慢指针这是判断是否有环最有效的方法。慢指针一次走一步快指针一次走两步。如果快指针能走到表尾则没有环。否则快慢指针在环中绕圈的时候总会碰到一起。两者相碰作为判定存在环的条件
public boolean hasCycle(ListNode head){
if (head null head.next null) return false;
ListNode fast head, slow head;
while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if (fastslow)return true;
}
return false;
}题目二环形链表II
题目链接 142.环形链表II
与上一题只有返回的内容不同 方法一、哈希表
可以利用哈希表遍历的时候把节点放进去。当有节点在哈希表出现过时该结点就是环的入口
public class Solution {public ListNode detectCycle(ListNode head) {ListNode node head;SetListNode set new HashSet();while(node ! null){if(set.contains(node)) return node;set.add(node);node node.next;}return null;}
}方法二、快慢指针重点 这里的问题是如果知道了一定有入口那么如何确定入口的位置呢方法非常简单但是要理解清楚有些难度。 结论先按照上面快慢方式寻找到相遇的位置(假设如下图中Z)然后将两指针分别放在链表头(X)和相遇位置(Z)并改为相同速度推进则两指针在环开始位置相遇Y)
推导过程
1.假设一圈就遇到为了便于理解我们首先假定快指针在第二次进入环的时候就相遇了.此时的过程是(1)找环中相汇点。分别用fast、slow表示快慢指针slow每次走一步fast就走两步直到在环中的某个位置相会假如是图中的Z。(2)第一次相遇那么我们可以知道fast指针走了abcb步slow指针走了ab步那么2*(ab)abcb所以ac因此此时让slow从Z继续向前走fast回到起点两个同时开始走两个每次都走一步)一次走一步那么它们最终会相遇在y点正是环的起始点。 2.如果多圈后相遇设链表中环外部分的长度为aslow指针进入环后又走了b的距离与fast相遇。此时fast指针已经走完了环的n圈因此它走过的总距离为Fast:an(bc)ba(n1)bnc根据题意任意时刻fast指针走过的距离都为slow指针的2倍。因此我们有a(n1)bnc2(ab)由于bc就是环的长度假如为len,则ac(n-1)*len这说明什么呢说明相遇的时候快指针在环里已经转了(n-1)圈如果n1就退化成了我们上面说的一圈的场景。假如n是2,3,4呢这只是说明当一个指针p1重新开始从head走的时候另一个指针p2从Z点开始p1、p2共速时两者会恰好在入口处相遇只不过p2要先在环中转n-1圈。
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head, slow head;while(fast ! null fast.next ! null){if(slow.next fast.next.next) break;slow slow.next;fast fast.next.next;}if(fast null || fast.next null) return null;ListNode node1 head, node2 slow.next;while(node1 ! node2){node1 node1.next;node2 node2.next;}return node1;}
}结语 如果对这道题分享对您有所帮助点个关注为会每天更新力扣题的分享与大伙儿一起进步
