Python链表中环的问题：3种方法判断是否有环，找到入环节点，...

链表相关文章： Python实现单向链表（上）：小白写法的15种增删改查操作 Python实现单向链表（下）：整合式实现增删改查操作

---

准备工作：创建结点（Node）类

class Node: def __init__(self, data, next=None): self.data = data # 数据，当前结点的元素 self.next = None # 指针，指向下一个结点

准备工作：创建一个有环的链表来测试

创建的是一个如下图所示的有环链表：

代码如下：

if __name__ == '__main__': node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node3 # 在这里调用下面要写的各种函数 # ...

判断链表中是否有环

方法1：用哈希表储存节点，遍历节点与哈希表中元素做对比

将所有的遍历过的节点用字典（哈希表）存储起来，然后每遍历一个节点，在字典中查找是否遍历过该节点。如果字典中存在该节点，说明链表中存在环；如果直到遍历结束，都未在字典中找到重复的节点，说明链表不存在环。

算法的时间复杂度为O(n)，空间复杂度为O(n)

代码：

def exist_circle1(head: Node): dic = {} cursor = head count = -1 while cursor.next: if cursor not in dic.values(): count += 1 dic[count] = cursor cursor = cursor.next else: return True return False

测试：

if __name__ == '__main__': node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node3 print(exist_circle1(node1)) # 输出：True

方法2：反转指针

每过一个节点就把该节点的指针反向。当有环的时候，最后指针会定位到链表的头部，如果到最后，都没有再到头部，那说明链表不存在循环。这个方法会破坏掉链表，所以如果要求是不能破坏链表的话，我们最后就还需要反转一下，再将链表恢复。

算法的时间复杂度为O(n)，空间复杂度为O(1)

如果有环： 如果没有环：

代码：

def exist_circle2(head: Node): current = head pre = None while current: next_node = current.next current.next = pre pre = current current = next_node if pre is head: return True else: return False

测试：

if __name__ == '__main__': node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node3 print(exist_circle2(node1)) # 输出：True

方法3：快慢指针

快慢指针方法，就是定义一个每次移动两个节点的快指针(fast)每次移动2个节点，和一个每次移动一个节点的慢指针(slow)。

如果不存在环，则快指针会更快地到达链表中的尾结点。如果存在环，快指针会先于慢指针进入环，并在环里面循环。慢指针进入环后，会和快指针在环内相遇。

算法的时间复杂度为O(n)，空间复杂度为O(1)。

注意这种方法只适用于环出现在链表尾部的情况，也就是单链表环的问题。

它无法解决链表存在循环的问题。原因如下列图示：

代码：

# 设置两个指针(slow, fast)，初始值都指向头，slow每次前进一步，fast每次前进二步， # 如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。 def exist_circle3(head: Node): fast = head slow = head while fast and fast.next: fast = fast.next.next slow = slow.next if slow is fast: # 两个指针相遇，存在环 return True # 两个指针未相遇，不存在环 return False

测试：

if __name__ == '__main__': node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node3 print(exist_circle3(node1)) # 输出：True

找到入环节点

使用方法3：快慢指针

数学证明： 如上图所示： 设头结点到入环点的距离为s； 设入环点到相遇点点距离为s1； 设相遇点到入环点点距离为s2

相遇时： 慢指针slow移动了 s + s1 ； 快指针fast移动了 s + s1 + n(s1 + s2)，其中n为快指针在环中已循环的圈数

同时我们知道，快指针一次移动两个节点，慢指针一次移动一个节点。因此快指针移动的距离是慢指针移动距离的2倍。

得到等式： 2(s + s1) = s + s1 + n(s1 + s2) 合并同类项后得到： s = (n - 1)(s1 + s2) + s2

分析上方得到的等式，左手边的s就是头结点到入环点的距离；右手边的(n - 1)(s1 + s2)是快指针在环中走过的整圈的距离，s2是快指针在环里除了整圈外又走的距离。

产生了一个想法：

如果在快指针和慢指针第一次相遇后，我们让一个指针（p1）回到链表头结点的位置，让另一个指针（p2）留在第一次相遇点。然后，现在让两个指针前进速度一致，都一次移动一个节点。那么两个指针就会在入环点再次相遇了！

好像说的不是很明白，rephrase一下：

s = (n - 1)(s1 + s2) + s2

等式左手边是p1会走过的距离，等式右手边是p2走过的距离。p1从头结点开始走，p2从第一次相遇点开始走。按照等式右手边所说，p2会在环里走几个整圈，然后当他又走了s2时，会和p1相遇。

代码：

def beginOfCircle(head): # 找到相遇点 fast = head slow = head while fast and fast.next: fast = fast.next.next slow = slow.next if slow is fast: # 两个指针相遇 # 这时候两个指针所在的点就是相遇点 break # 找到入环点 slow = head # 让慢指针回到头节点 # 现在让快慢指针都每次移动一个节点 # 它们会在入环点再次相遇 while slow != fast: slow = slow.next fast = fast.next return slow

---

Info Author: Shanshan Yan Wechat: shanshan700224 Copyright: All rights reserved