docs-isharkfly-com/algorithm/linked-list-cycle.md

4.4 KiB
Raw Permalink Blame History

带环链表Linked List Cycle

🔔 参与讨论:https://www.isharkfly.com/t/linked-list-cycle/15122

描述

给定一个链表,判断它是否有环。

样例

给出 -21->10->4->5, tail connects to node index 1返回 true。

这里解释下题目的意思在英文原题中tail connects to node index 1 表示的是节点 5 还要链接回索引号 为 1 的节点。

一个典型的带环链表如下:

挑战

不要使用额外的空间

代码

GitHub 的源代码,请访问下面的链接: https://github.com/honeymoose/codebank-algorithm/blob/main/src/test/java/com/ossez/codebank/algorithm/tests/lintcode/LintCode0102HasCycleTest.java

点评

链表Linked list是一种常见的基础数据结构是一种线性表但是并不会按线性的顺序存储数据而是在每一个节点里存到下一个节点的指针( Pointer)。由于不必须按顺序存储链表在插入的时候可以达到O(1) 的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要O(n) 的时间而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

在计算机科学中链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成每个节点包含任意的实例数据data fields和一或两个用来指向上一个/或下一个节点的位置的链接”links”。链表最明显的好处就是常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型因为它包含指向另一个相同类型的数据的指针链接。链表允许插入和移除表上任意位置上的节点但是不允许随机存取。链表有很多种不同的类型单向链表双向链表以及循环链表。

要判断一个链表中是否有循环,可以借助额外的存储空间,将链表插入到 HashSet 中。创建一个以节点ID为键的HashSet集合用来存储曾经遍历过的节点。然后同样是从头节点开始依次遍历单链表的每一个节点。每遍历到一个新节点就用新节点和HashSet集合当中存储的节点作比较如果发现HashSet当中存在相同节点ID则说明链表有环如果HashSet当中不存在相同的节点ID就把这个新节点ID存入HashSet之后进入下一节点继续重复刚才的操作。

这个方法在流程上和方法一类似本质的区别是使用了HashSet作为额外的缓存。

假设从链表头节点到入环点的距离是D链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S) =D+S可以简单理解为O(N)。而算法的空间复杂度还是D+S-1可以简单地理解成O(N)。

也可以采用指针的方式。

首先创建两个指针1和2在java里就是两个对象引用同时指向这个链表的头节点。然后开始一个大循环在循环体中让指针1每次向下移动一个节点让指针2每次向下移动两个节点然后比较两个指针指向的节点是否相同。如果相同则判断出链表有环如果不同则继续下一次循环。

例如链表A->B->C->D->B->C-> D两个指针最初都指向节点A进入第一轮循环指针1移动到了节点B指针2移动到了C。第二轮循环指针1移动到了节点C指针2移动到了节点B。第三轮循环指针1移动到了节点D指针2移动到了节点D此时两指针指向同一节点判断出链表有环。

此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。