南京华夏天成建设有限公司网站,怎么可以创建网站,昆明小程序开发制作公司,大学生网站开发工作室总结环形链表:
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 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 105pos 为 -1 或者链表中的一个 有效索引 。
进阶你能用 O(1)即常量内存解决此问题吗 自己解的时间复杂度为:O(n)
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {HashMapListNode,Boolean mapnew HashMap(); public boolean hasCycle(ListNode head) {while(map.get(head)nullhead!null){map.put(head,true);headhead.next;}return headnull?false:true;}
}
需要时间复杂度为O(1)就需要使用快慢针需要对 Floyd 判圈算法又称龟兔赛跑算法
所以我们首先来认识一下Floyd判圈算法
给定一个带环的链表判断该环的入口 首先将两个指针toriose和hare分别指向链表头然后持续执行一下步骤
hare前进两一步toriose前进一步在有限次步骤下hare与toriose会在环上相遇此时 此时我们需要一个新的指针指向链表的头持续执行一下步骤
新指针toriose前进一步相遇点的指针前进一步 在有限次步骤下新指针toriose与相遇点的指针hare会在环的入口相遇
证明
第一步很简单一个快指针和一个慢指针在环上循环一定会在某个时刻快指针追上了慢指针
第二步 相遇点与新指针等速将会在环的出口相遇 对于这道题只需要判断链表是否有环只需要设置一个快慢指针当两个指针相遇的时候就是有环如果走到后面快指针为空那就是无环
设计代码如下
/*** 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 fasthead.next;ListNode slowhead;while (slow ! fast) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;}
}
