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

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

---

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

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

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

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

代码如下：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

判断链表中是否有环

方法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
1
2
3
4
5
6
7
8
9
10
11
12

测试：

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法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
1
2
3
4
5
6
7
8
9
10
11
12

测试：

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法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
1
2
3
4
5
6
7
8
9
10
11
12
13

测试：

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

找到入环节点

使用方法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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

Info

Author: Shanshan Yan

Wechat: shanshan700224

Copyright: All rights reserved