做微信推文的网站,自己做彩票网站合法吗,建设私人网站,免费ip地址代理软件Suffering, for the weak is the tomb of death, and for the strong is the soil of germinal ambition.
1. 题目描述 2. 题目分析与解析
2.1 思路一
这个题目就是判断一个链表有没有环#xff0c;其实我们之讲过一个题目#xff0c;就实现了判断链表有没有环的步骤其实我们之讲过一个题目就实现了判断链表有没有环的步骤面试经典150题——快乐数并且还有图示就是使用快慢指针法因此在本篇文章中就不过多赘述了直接给出代码思路。
代码思路 定义两个指针分别表示快慢指针 让快指针以2的速度前进慢指针以1的速度前进 如果两个指针相交说明链表中存在环结构返回true 如果遍历到结尾仍然没有返回false就说明没有环返回false
2.2 思路二
因为我们用一种很简单的思路如何判断自己是否在一个地方转圈一个很好的方法就是在我们开始走的位置做一个标记用来标注我们之前走过这个地方如果未来我们又能发现这个标记那么就说明我们绕圈了。
把这种思路对应在题目中就是设置一个标记来表示我是否走过这个地方如果走过我在后续遍历过程中又能回到这个地方那么就说明链表存在环状结构如果走到目的地结尾发现还是没有经历过标记点那么就说明不存在环状结构返回false。
如何标记因为我们走的每一个点是一个ListNode对象而对象的唯一标识就是它的引用或者hash值了吧因此我们可以使用一个hashMap用来存储每一个走过位置的hash如果在后续遍历过程中还能匹配到之前走过的hash那么就说明出现环状结构了。
代码思路 定义一个hashMap 遍历链表没走过一个节点之前先判断该节点是否在hashMap存在如果存在直接返回true 如果遍历完毕所有节点都没有返回false那么说明不存在环状结构返回false
3. 代码实现
3.1 思路一 3.2 思路二
使用哈希表——对比引用 使用哈希表——对比hash值 4. 相关复杂度分析
对于给出的三种解决环形链表问题的方法我们来分析它们的时间和空间复杂度
思路1使用快慢指针 时间复杂度O(n)其中 n 是链表的长度。快指针每次移动两步慢指针每次移动一步因此快指针最多移动 n/2 次慢指针最多移动 n 次整体遍历的时间复杂度为 O(n)。 空间复杂度O(1)只使用了常数级别的额外空间。
思路2使用哈希表对比引用 时间复杂度O(n)其中 n 是链表的长度。遍历链表需要 O(n) 的时间同时在哈希表中查找节点是否存在的时间复杂度是 O(1)。 空间复杂度O(n)需要使用一个哈希表来存储链表中的节点因此空间复杂度是 O(n)其中 n 是链表的长度。
思路3使用哈希表对比哈希值 时间复杂度O(n)其中 n 是链表的长度。与思路2相似遍历链表需要 O(n) 的时间同时在哈希表中查找哈希值是否存在的时间复杂度是 O(1)。 空间复杂度O(n)需要使用一个哈希表来存储链表中的节点的哈希值因此空间复杂度是 O(n)其中 n 是链表的长度。
