AI智能
改变未来

100天精刷LeetCode-Day6:Linked List Cycle2问题(附详细思路和python题解)


142 Linked List Cycle

题目描述

思路

  • 依然用快慢指针的思路,然而这次需要考虑的是环的入口,这时候有一个更巧妙的方法:当快慢指针相遇时,一个从head出发的慢指针_2以与慢指针相同的速度出发。当两个指针相遇的时候,所在node就是cycle的入口。

慢指针:A——>B—–>C(共走了N步)

快指针:A——>B—–>C(共走了2N步)

快指针fast比慢指slow针多走了N步,因此,慢指针slow如果继续再走N步,会从C—–>C,依然回到C点相遇点;

现在我们再设一慢指针slow2(方便起见可以重新定义之前的快指针)从A点出发,和原慢指针slow以相同步长移动,原来的慢指针slow继续从相遇点C往前走;

slow2经过N步之后到达C,slow经过N步之后也到达C,我们考察一下两个指针的轨迹:

slow:C—–>B——>C

slow2:A—–>B——>C

由此可见,两个指针若想要在C点相遇,其必要条件就是在B点(环入口)就相遇,然后“携手”走完B——>C的路程。

代码

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:if not head or not head.next: return Nonefast = slow = slow1 = ListNode(0)fast.next = headslow.next = headslow1.next = heads = 0while fast:if not fast.next: return Nonefast = fast.next.nextslow = slow.nexts += 1if fast == slow:breakwhile slow1 != slow:if not slow: return Noneslow1 = slow1.nextslow = slow.nextreturn slow

收获

边界条件一定要考虑清楚,这道题思路有了但是三个边界条件卡了很久。建议想清楚算法之后首先考虑边界条件。

赞(0) 打赏
未经允许不得转载:爱站程序员基地 » 100天精刷LeetCode-Day6:Linked List Cycle2问题(附详细思路和python题解)