网站开发前端就业前景,网络游戏开发培训,优化合作平台,wordpress 动态效果这里写目录标题 判断链表中是否有环描述代码检测链表中是否存在环链表中存在环想检测链表中是否存在环#xff0c;而不需要找到环的入口 判断链表中是否有环
题目
描述
判断给定的链表中是否有环。如果有环则返回true#xff0c;否则返回false。
数据范围#xff1a;链表… 这里写目录标题 判断链表中是否有环描述代码检测链表中是否存在环链表中存在环想检测链表中是否存在环而不需要找到环的入口 判断链表中是否有环
题目
描述
判断给定的链表中是否有环。如果有环则返回true否则返回false。
数据范围链表长度 0≤n≤10000链表中任意节点的值满足
∣val∣100000 要求空间复杂度 O(1)时间复杂度 O(n)
输入分为两部分第一部分为链表第二部分代表是否有环然后将组成的head头结点传入到函数里面。-1代表无环其它的数字代表有环这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时对应的链表结构如下图所示
可以看出环的入口结点为从头结点开始的第1个结点注头结点为第0个结点所以输出true。 示例1 输入 {3,2,0,-4},1 返回值 true 说明第一部分{3,2,0,-4}代表一个链表第二部分的1表示-4到位置1注头结点为位置0即-4-2存在一个链接组成传入的head为一个带环的链表返回true 示例2 输入{1},-1 返回值false 说明 第一部分{1}代表一个链表-1代表无环组成传入head为一个无环的单链表返回false 示例3 输入{-1,-7,7,-4,19,6,-9,-5,-2,-5},6 返回值true 代码
import java.util.*;/*** 定义了链表节点的类。* 每个节点包含一个整数值和一个指向下一个节点的引用。*/
class ListNode {int val; // 节点存储的值ListNode next; // 指向下一个节点的引用// 构造函数用于创建一个新的节点初始化其值和下一个节点的引用ListNode(int x) {val x;next null;}
}public class Solution {/*** 检测链表中是否存在环。* param head 链表的头节点。* return 如果链表中存在环返回true否则返回false。*/public boolean hasCycle(ListNode head) {// 如果头节点为空则链表不存在环if (head null) {return false;}// 初始化两个指针fast和slow它们都指向头节点ListNode fast head;ListNode slow head;// 使用循环进行检测直到fast和slow相遇或者fast到达链表末尾do {// 如果fast的下一个节点或者下下个节点为空说明链表没有环if (fast.next null || fast.next.next null) {return false;}// 移动fast指针每次移动两步fast fast.next.next;// 移动slow指针每次移动一步slow slow.next;} while (fast ! slow); // 如果fast和slow相遇说明存在环// 如果循环结束fast没有和slow相遇说明链表没有环return true;}
}检测链表中是否存在环
使用的是快慢指针也称为龟兔赛跑算法来检测链表中是否存在环。以下是快慢指针相遇的逻辑详细解释 初始化我们有两个指针fast和slow它们都从链表的头节点开始。 移动指针 fast指针每次移动两步即fast fast.next.next。slow指针每次移动一步即slow slow.next。 相遇条件 如果链表中存在环那么fast指针和slow指针最终会相遇。这是因为fast指针移动的速度是slow指针的两倍所以它们会在环内相遇。如果链表中没有环fast指针会先到达链表的末尾即fast或fast.next为null此时fast和slow不会相遇。 检测逻辑 在每次循环中我们首先检查fast指针的下一个节点或下下个节点是否为null。如果为null则说明链表没有环直接返回false。如果fast指针的下一个节点或下下个节点不为null则继续移动fast和slow指针。当fast和slow指针相遇时说明链表中存在环返回true。 结束条件 如果fast指针在移动过程中到达了链表的末尾即fast或fast.next为null则说明链表中没有环返回false。
通过这种方式快慢指针算法能够有效地检测出链表中是否存在环并且时间复杂度为O(n)空间复杂度为O(1)。 链表中存在环
如果链表中存在环并且fast和slow指针相遇接下来的处理取决于你想要完成的具体任务。以下是一些常见的处理方式 检测环的长度 一旦fast和slow相遇你可以继续移动其中一个指针通常是slow每次移动一步直到再次遇到环的起点。这样你可以计算出环的长度。 找到环的入口 你可以在fast和slow相遇后将其中一个指针通常是fast重新指向头节点然后同时移动fast和slow每次移动一步。当它们再次相遇时相遇点就是环的入口。 删除环 如果你的目标是删除环可以在找到环的入口后通过调整指针来删除环。例如你可以将环的最后一个节点的next指针设置为null。 重新初始化指针 如果你只是需要检测环的存在那么在fast和slow相遇后你可以直接返回true。
以下是一些示例代码展示如何在fast和slow相遇后找到环的入口
public class Solution {public boolean hasCycle(ListNode head) {if (head null) {return false;}ListNode fast head;ListNode slow head;while (fast ! slow) {if (fast null || fast.next null) {return false;}fast fast.next.next;slow slow.next;}// fast 和 slow 相遇重新初始化 fast 指向头节点fast head;// 当 fast 和 slow 再次相遇时相遇点就是环的入口while (fast ! slow) {fast fast.next;slow slow.next;}// 返回 true 表示链表中有环return true;}
}在这个示例中一旦fast和slow相遇我们将fast重新指向头节点然后同时移动fast和slow直到它们再次相遇。这时的相遇点就是环的入口。这种方法可以确保你找到环的入口而不仅仅是检测环的存在。 想检测链表中是否存在环而不需要找到环的入口
如果你只想检测链表中是否存在环而不需要找到环的入口你可以简化代码只保留检测环存在的逻辑。以下是修改后的代码示例
public class Solution {/*** 检测链表中是否存在环。* param head 链表的头节点。* return 如果链表中存在环返回true否则返回false。*/public boolean hasCycle(ListNode head) {if (head null) {return false;}// 初始化两个指针fast和slow它们都指向头节点ListNode fast head;ListNode slow head;// 使用循环进行检测直到fast和slow相遇或者fast到达链表末尾while (fast ! null fast.next ! null) {// 移动fast指针每次移动两步fast fast.next.next;// 移动slow指针每次移动一步slow slow.next;// 如果fast和slow相遇说明存在环if (fast slow) {return true;}}// 如果fast到达链表末尾说明没有环return false;}
}在这个修改后的代码中我们只保留了循环直到fast指针到达链表的末尾或fast和slow相遇。如果fast和slow相遇函数立即返回true表示链表中存在环。如果fast到达链表的末尾即fast或fast.next为null则循环结束函数返回false表示链表中没有环。
这种方法的时间复杂度是O(n)空间复杂度是O(1)非常高效。
