共计 1871 个字符,预计需要花费 5 分钟才能阅读完成。
题目
给定一个链表的头节点 head,返回链表开始入环的第一个节点。如果链表无环,则返回 null。
如果链表中有某个节点,能够通过间断跟踪 next 指针再次达到,则链表中存在环。为了示意给定链表中的环,评测零碎外部应用整数 pos 来示意链表尾连贯到链表中的地位(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。留神:pos 不作为参数进行传递,仅仅是为了标识链表的理论状况。
输出:head = [3,2,0,-4], pos = 1
输入:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连贯到第二个节点。输出:head = [1], pos = -1
输入:返回 null
解释:链表中没有环。
遍历 + 哈希
最简略的方法就是遍历每个节点,同时把节点存到一个字典中,当遍历下一个节点时,看看该节点是否曾经存在于字典中,如果是,就阐明该节点是环入口节点
def detectCycle(head: ListNode) -> ListNode:
hashTable = {}
while head:
if head in hashTable:
return head
hashTable[head] = 1
head = head.next
return None
工夫复杂度:O(n)
空间复杂度:O(n)
双指针
了解双指针的思路,须要通过画图,计算挪动间隔的等量关系来了解:
在链表头节点,定义两个指针:fast 和 slow
fast 每次挪动 2 个节点,slow 每次挪动 1 个节点
如果链表没有环,fast 指针会先挪动到 null 处
如果链表有环,fast 先进入环,slow 随后进入环,最终他们必定会在环中的某个节点相遇
假如 fast 和 slow 第一次相遇时的节点如图所示
a 代表链表头节点到环的入口节点的节点数
b 代表环的入口节点到 fast 和 slow 第一次相遇的节点的节点数
c 代表第一次相遇节点到环的入口节点的节点数
此时,fast 走过的节点数为 a+b+n(c+b),n 示意 fast 在环中绕的圈数
slow 走过的节点数为 a+b
fast 和 slow 是一起挪动的,所以任意时刻他们的挪动步数是雷同的,然而 fast 每次挪动 2 个节点,雷同的步数下,fast 挪动的节点数应该是 slow 的 2 倍
所以 a+b+n(c+b) = 2(a+b)
整顿等式得:a=n(b+c)-b = nb+nc-b = (n-1)b+nc = (n-1)b+(n-1)c+c=(n-1)(b+c)+c
得 a = (n-1)(b+c)+c
也就是说:头节点到环入口节点的间隔 = 第一次相遇节点到环入口节点的间隔 +(n-1)圈环的长度
如果此时有两个指针 a 和 b,a 从头节点开始挪动,b 从 slow 和 fast 第一次相遇节点开始挪动,均每次挪动一个节点,a 和 b 最终会在环入口节点处相遇。
此时,slow 曾经处在第一次相遇节点地位,因而当 slow 和 fast 第一次相遇时,再在头节点处定义一个指针,和 slow 一起每次挪动 1 个节点,他们相遇的那个节点就是环入口节点。
def detectCycle(self, head: ListNode) -> ListNode:
# 排除空链表状况
if not head:
return None
fast,slow,ptr = head,head,head
while fast:
# 排除链表只有一个节点的状况
if not fast.next:
return None
# 挪动 fast 和 slow
slow = slow.next
fast = fast.next.next
# fast 和 slow 相遇时
if slow == fast:
# ptr 和 slow 开始挪动,直到相遇
while ptr != slow:
slow = slow.next
ptr = ptr.next
# 相遇时,返回该节点,就是入口节点
return ptr
return None
# 跟简洁优雅版
def detectCycle(self, head: ListNode) -> ListNode:
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
工夫复杂度:O(N),其中 N 为链表中节点的数目。在最后判断快慢指针是否相遇时,slow 指针走过的间隔不会超过链表的总长度;随后寻找入环点时,走过的间隔也不会超过链表的总长度。因而,总的执行工夫为 O(N)+O(N)=O(N)。
空间复杂度:O(1)。咱们只应用了 slow,fast,ptr 三个指针。