思路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