[leetcode链表系列]3 链表成环

本文涉及知识点　

• hash结构
• 链表

两种数据结构在前面的相关内容都有所提及，如果忘记了，复习完再看效果一定翻倍哟！

1

Leetcode141 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例1：

输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。

小蓝希望大家在此思考1分钟，

效果更好哈！

01 题目解析

仔细读题，所谓成环，可能是循环单链表(首尾成环)，也有可能部分成环，即尾部与部分结点相连。

• 解法1
  • 看过前面相关内容的小伙伴一定很快想到的方法是使用hash数据结构来存储每个访问过的节点，如果某个节点的地址出现在了哈希表中，那么再次出现的那个节点就是我们要找的成环的起点了。
• 解法2
  • 我们假设两小朋友，小蓝和小小从同一地点直线出发如下图，一路前进，所阅风景只能各自独自欣赏了。

• 两位为了将自己所听所闻所见随时告诉对方，但是小蓝走的快一点，一次走两步,小小一次走一步，那么在这个圆环中总有一次机会让小蓝遇见小小，从而开始分享自己的浪漫故事。如下图所示。如果描述的不算清晰，我们继续往下看，画图进一步理解。

• 解法2图解
  • 我们假设一个快指针p和慢指针q，如果无环，那么各自走各自的路直到最后NULL也不会相遇。
  • 如果有环，快指针自然走的快，一旦进入环，快指针可能在慢指针前面，也可以在慢指针后面直到相遇。以[3,2,0,4]为例，p一次走两步，q一次走一步，如下图。

• 为什么快指针是走两步，慢指针走一步，为啥是两倍？五倍不香？因为如果五倍，快指针将更快的进入环，就会长时间在环内做无用功等待慢指针的到来。

02 代码实现

1 c++版本

2 python版本

3 java版本