【leetcode 142】 Linked List Cycle II 链表找环

本文主要是介绍【leetcode 142】 Linked List Cycle II 链表找环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表找环

https://leetcode.com/problems/linked-list-cycle-ii/

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: bool"""p1 = headp2 = headwhile p1 is not None and p1.next is not None:p1=p1.next.nextp2=p2.nextif p1==p2:breakif p1==None or p1.next==None:return Nonep1 = headwhile p1!=p2:p1=p1.nextp2=p2.nextreturn p1

解释：

快慢指针发，p1每次移动两个节点，p2每次移动一个节点，p1、p2必然相遇。相遇时如上图所示，另|AB|=l0，p1能追上p2说明p1比p2多走了整数倍的圈数，若假设一圈的长度为c，则 $\Delta l=kc$，此时，从链表头到A的距离为$kc-l_0$，同时p2到A的距离为$c-l_0$，若让p1从表头开始以一次一个节点的速度移动，p2的速度不变，继续移动，p1、p2的相遇节点恰好为A，即环的起始节点(p2多走几圈无所谓)。

这篇关于【leetcode 142】 Linked List Cycle II 链表找环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---