思路1 双指针循环相遇
时间复杂度 O(n)
空间复杂度 O(1)
太6了,我的理解:
两个链表长度分别为L1+C、L2+C, C为公共部分的长度,
按照楼主的做法: 第一个人走了L1+C步后,回到第二个人起点走L2步;第2个人走了L2+C步后,回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了
即最后两个人都会走L1 + L2 + C步
如果C = 0,两个人都走了L1 + L2步后,p1 == p2 == None也会跳出循环
Last updated
时间复杂度 O(n)
空间复杂度 O(1)
太6了,我的理解:
两个链表长度分别为L1+C、L2+C, C为公共部分的长度,
按照楼主的做法: 第一个人走了L1+C步后,回到第二个人起点走L2步;第2个人走了L2+C步后,回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了
即最后两个人都会走L1 + L2 + C步
如果C = 0,两个人都走了L1 + L2步后,p1 == p2 == None也会跳出循环
Last updated