142. 环形链表 II（Python3）

Problem: 142. 环形链表 II

思路

哈希表+单指针

1. 链表本身读写困难，因此通过遍历先存入散列表；

2. 在循环中判断是否有环，并返回环的入口节点。

快慢指针

参考：

• 环形链表II【基础算法精讲 07】

• 环形链表 II（双指针，清晰图解）

• 有一定技巧的数学思考，重点关注：

1. 第一次相遇慢指针未走过一个环长；

2. 第二次相遇一定发生在环的入口处。

Code

哈希表+单指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        
        visited = set() # 初始化散列表
        temp = head # 指针指向head

        while temp: # 循环遍历进行判断与存储
            if temp in visited: # 若访问过，则返回节点（入环口节点）
                return temp
            
            visited.add(temp) # 添加节点进入散列表
            temp = temp.next # 移动指针

        return None # 没有访问过，则返回 None

快慢指针1 参考灵神

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        
        slow = fast = head # 初始化双指针

        while fast and fast.next: # 判断有环的关键条件
            
            slow = slow.next    # 慢指针
            fast = fast.next.next   # 快指针

            if fast is slow:    # 快慢指针在环中相遇

                while head is not slow: # 快慢指针相遇后移动慢指针和头部指针
                    head = head.next    
                    slow = slow.next
                
                return slow # 头部指针和慢指针必然在环入口处相遇
            
        return None

快慢指针2 参考K神

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        
        slow = fast = head # 初始化双指针

        while True:
            if not (fast and fast.next): return None # 无环
            slow, fast = slow.next, fast.next.next
            if slow is fast: break  # 环中第一次相遇

        fast = head # 重新指向head
        while slow is not fast: # 环入口处第二次相遇
            slow, fast = slow.next, fast.next
        
        return slow