leetcode 142. Linked List Cycle II

    科技2022-07-10  101

    题意: 判断一个链表中有没有环,有返回环的起始节点。 解法: 用快慢指针判断是否是环,不是则返回NULL,是则返回相遇时的节点。然后另设一个节点指向头结点,两个节点同时走一步,走到相同的节点即为环的起始节点。 设链表到环的起始节点的距离为x,环内起始节点到快慢指针相遇节点的距离为y,剩下距离为z。则 2 ( x + y ) = x + y + z + y 2(x+y)=x+y+z+y 2(x+y)=x+y+z+y,得到 x = z x=z x=z。即第一次相遇时,距离起始节点的距离为x。 总结: 这一题还可以通过集合来求解,但是这种方法更简洁,空间使用更少。需要通过数学方式理解。

    Processed: 0.013, SQL: 8