如何使用示例在Java中的链表中检测循环
如果您想练习数据结构和算法程序，可以通过 数据结构和算法面试题.
当今最受欢迎的面试问题之一是“如何在LinkedList中检测循环/循环”。所以我认为我应该解决这个问题。这个问题与数据结构更相关。您也可以找到 循环的起始节点 如果循环存在。
爪哇链表面试程序：
- 如何在Java中反向链接列表
- 如何成对反向链接列表
- 如何在Java中找到链表的中间元素
- 如何在Java中的链表中检测循环
- 在链表中查找循环的开始节点
- 如何从链表的末尾查找第n个元素
- 如何在Java中检查链表是否是回文
- 在Java中添加两个由链表表示的数字
第一种方法 您可能认为可能是这样：
- 遍历每个节点直到结束，使用访问标记跟踪访问的节点。
- 如果找到已经访问过的节点，则LinkedList中有一个循环；如果遍历时到达终点，则LinkedList中没有循环
但是上述方法的问题是，在大多数情况下，您无法更改LinkedList节点的数据结构，因此您赢得了’不能向其添加访问标记。
高效的方法：
弗洛伊德将是解决这个问题的有效方法’的周期检测算法，因此该算法的步骤为：
- 使用两个指针fastPtr和slowPtr并将其初始化为链表的开头
- 在每次迭代中，将fastPtr移动两个节点，将slowPtr移动一个节点。
- 如果fastPtr和slowPtr在某个迭代中相遇，则链表中会有一个循环。
- If fastPtr reaches to the end of linkedlist without meeting slow pointer then there is no loop in linkedlist (i.e fastPtr->下一页 or fastPtr->下一页->下一页 become 空值)
该算法的Java代码将是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
上市 布尔值 如果LoopExists() { 节点 fastPtr = 头; 节点 慢点 = 头; 而 (fastPtr ！= 空值 && fastPtr.下一页 ！= 空值) { fastPtr = fastPtr.下一页.下一页; 慢点 = 慢点.下一页; 如果 (慢点 == fastPtr) 返回 真正; } 返回 假; } |
以上解决方案在o（n）时间复杂度和o（1）空间复杂度下工作。
让我们创建没有循环的链表：
让我们创建一个名为 “LinkedList.java”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
包 组织.Arpit.爪哇2blog; 上市 类 链表{ 私人的 节点 头; 私人的 静态的 类 节点 { 私人的 整型 值; 私人的 节点 下一页; 节点(整型 值) { 这个.值 = 值; } } 上市 虚空 addToTheLast(节点 节点) { 如果 (头 == 空值) { 头 = 节点; } 其他 { 节点 温度 = 头; 而 (温度.下一页 ！= 空值) 温度 = 温度.下一页; 温度.下一页 = 节点; } } 上市 虚空 打印列表() { 节点 温度 = 头; 而 (温度 ！= 空值) { 系统.出.格式(“％d”, 温度.值); 温度 = 温度.下一页; } 系统.出.打印(); } 上市 布尔值 如果LoopExists() { 节点 fastPtr = 头; 节点 慢点 = 头; 而 (fastPtr ！= 空值 && fastPtr.下一页 ！= 空值) { fastPtr = fastPtr.下一页.下一页; 慢点 = 慢点.下一页; 如果 (慢点 == fastPtr) 返回 真正; } 返回 假; } 上市 静态的 虚空 主要(串[] args) { 链表 清单 = 新 链表(); //创建链接列表 清单.addToTheLast(新 节点(5)); 清单.addToTheLast(新 节点(6)); 清单.addToTheLast(新 节点(7)); 清单.addToTheLast(新 节点(1)); 清单.addToTheLast(新 节点(2)); 清单.打印列表(); //测试循环是否存在 系统.出.打印(“循环存在->" + 清单.如果LoopExists()); } } |
从逻辑上讲，我们的链表可以表示为：
运行上面的程序，您将获得以下输出：
|
1 2 3 4 |
5 6 7 1 2 循环 存在->假 |
让我们在链表中创建一个循环
现在我们将最后一个节点连接到值为7的节点，它将在链表中创建循环，因此将上述main方法更改为：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
上市 静态的 虚空 主要(串[] args) { 链表 清单 = 新 链表(); //创建链接列表 节点 loopNode=新 节点(7); 清单.addToTheLast(新 节点(5)); 清单.addToTheLast(新 节点(6)); 清单.addToTheLast(loopNode); 清单.addToTheLast(新 节点(1)); 清单.addToTheLast(新 节点(2)); 清单.打印列表(); //创建一个循环 清单.addToTheLast(loopNode); //测试循环是否存在 系统.出.打印(“循环存在->" + 清单.如果LoopExists()); } |
从逻辑上讲，我们的带有循环的链表可以表示为：
运行上面的程序，您将获得以下输出：
|
1 2 3 4 |
5 6 7 1 2 循环 存在->真正 |
这样便可以在链表中检测到循环。
请通过 爪哇面试程序 有关更多此类程序。
Comments
addToLast将不添加节点。请检查
它被添加
在几种情况下，这看起来像是错误的
这将适用于奇数循环，如果循环像这样存在？
5->6->7>8>1>5>6