超简洁题解 | 5行代码搞定 #两个链表的第一个公共结点#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): p1, p2 = pHead1, pHead2 while p1 != p2: p1 = pHead2 if p1 is None else p1.next p2 = pHead1 if p2 is None else p2.next return p2
解题思路:
设 A 的长度为 a + c,B 的长度为 b + c,其中 c 为尾部公共部分长度,可知 a + c + b = b + c + a。
当访问链表 A 的指针访问到链表尾部时,令它从链表 B 的头部重新开始访问链表 B;同样地,当访问链表 B 的指针访问到链表尾部时,令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
python3解法,思路来自:CS2018。