142. 环形链表 II
已解答
中等
相关标签
相关企业
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# seen =set()
# p=head
# while p!=None:
# if p in seen:
# return p
# else:
# seen.add(p)
# p=p.next
# return None
"""
如何用空间复杂度1实现
"""
# 快慢指针可以吗
fast ,slow =head,head
while True:
if not (fast and fast.next): return
fast , slow = fast.next.next, slow.next
if fast==slow: break
fast = head
while fast!=slow:
fast,slow =fast.next,slow.next
return fast
这里是两种方法，第二种 快慢指针，非常男想到啊，需要列出公式，然后推理得到，在快慢指针相遇之后，在经过环外面的路径的长度的话，会到达相交节点
