Leetcode 刷题（6）简单单链表：找环形列表入口

题目

142. 环形列表II

难度： 中等

题目分析：使用额外空间，是最简单的方法，联系上一篇博客判读环形列表 使用额外空间的分析，在确认了有环的同时，第一个重复点，就是环的入口。

这道题同时有个非平凡的解法，基于使用快慢指针的解法，然后多定义两个指针，即能找到入口。

详细的图解和分析点这里

解法一： 使用额外空间

# 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:
    # 使用额外空间
        if head is None:
            return None
        
        visited = set()
        p = head
        while p:
            if p in visited:
                return p
            # 不在的话，存入
            visited.add(p)
            p = p.next
        
        return None # 出来说明没有环

运行效果：

注：不要太在意时间，不准的……

解法二： 快慢指针

# 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:
    # 阶段一：确认链表是否有环，同时返回两个指针重合的位置
    def get_meetpoint(head):
    	if not head: # 空列表
    		return None
    	fast = head
    	slow = head
    	while fast and fast.next:
    		slow = slow.next
    		fast = fast.next.next # 走两步
    		if slow == fast:
    		 	# 确认有环，同时返回位置
    			return slow
    	return None

	# 阶段二，定义新的指针，走到入口。
	# 这里代码基于相遇点离环形入口的距离等于链表头到环形入口距离，有严格数学证明，很巧妙，建议去查看
	meetpoint = get_meetpoint(head)
	if not meetpoint: # 不存在环
		return None # 自然没入口
	
	# 定义两个新指针，走到入口
	ptr1 = meetpoint
	ptr2 = head
	while ptr1 != ptr2:
		ptr1 = ptr1.next
		ptr2 = ptr2.next
	return ptr1

总结：

这道题，重点考察双指针技术，技巧性比较强，不过，一旦掌握方法，重复解出来就很快了。

运行结果