【完虐算法】两个链表的第一个公共结点
更多算法题解，请关注公众号《程序员学长》
两个链表的第一个公共结点
问题描述
LeetCode 剑指 Offer 52. 两个链表的第一个公共节点
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
要求：空间复杂度是O(1)，时间复杂度是O(m+n)。
示例：
文章图片
分析问题
这个问题最直观的想法就是遍历链表headA，然后把headA中的所有每个节点都加入到集合中。然后再循环遍历链表headB，判断结点是否在集合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，继续遍历，直到结束。如果headB的所有结点都不在集合中，则表明不相交，直接返回null。
def getIntersectionNode(headA,headB):
nodes=set()
while headA:
nodes.add(headA)
headA=headA.next
while headB:
if nodes.__contains__(headB):
return headB
headB=headB.next
return None该算法的时间复杂度是O(m+n)，空间复杂度是O(n)。其中m和n分别是链表headA和headB的长度。
由于题目要求时间复杂度是O(m+n)，空间复杂度是O(1)。我们这里可以使用双指针法将空间复杂度降低到O(1)。我们分别用两个指针p1和p2分别指向headA和headB，然后同时移动指针p1和p2。当p1到达headA的末尾时，让p1指向headB，当p2到达headB的末尾时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。
Tips:假设headA不相交的部分是a，headB不相交的部分是b，公共部分是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，可以知道p1和p2指针同时到达第一个公共结点；当a不等于b时，在p1移动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，然后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。
文章图片
def getIntersectionNode(headA,headB):
p1 = headA
p2 = headBwhile p1 != p2:
if p1:
p1=p1.next
else:
p1=headB
if p2:
p2=p2.next
else:
p2=headA
return p1【【完虐算法】两个链表的第一个公共结点】更多算法题解，请关注公众号《程序员学长》
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长