目录：
目的
思路
复杂度
记忆秘诀
python%E4%BB%A3%E7%A0%81-toc">python代码
目的
两个无环的单向链表，它们的第一个公共结点{{6,7}。
思路
这个任务是找到两个链表的第一个公共结点。可以看作两个心机boy偷偷补课翻车事件。平时嘴上说自己在家玩游戏，实际上背地里都偷偷上各种补习班。小明有一套补习pHead1，小红有一套补习pHead2。他们不仅上完自己的课，还要偷偷上对方的，要卷死对方，但是他们忽略了一点，如果有共同的补习班会再某时候碰上，就要翻车社死了。
心机boys登场：
-
小明（p1指针）：小明有一套自己的补习计划 pHead1，从头到尾按照顺序上课。
-
小亮（p2指针）：小亮则有另一套补习计划 pHead2，也是从头开始按顺序上课。
开始补课：
先完成自己的补课计划：
小明和小亮各自按照自己的计划上课p1 = p1.next，p2 = p2.next。偷偷上对方的课：
当小亮上完所有补习班后，他偷偷跑到小亮的第一个补习班继续补课p1 = pHead2；
同样，小亮也偷偷跑到小亮 的第一个补习班继续补p2 = p2.next。
翻车时刻：
-
翻车时刻p1 == p2：
如果有共同的补习班，他们迟早会在这个补习班里翻车碰面社死。这个补习班就是他们的“第一个公共节点”。-
为什么一定会翻车？（具体可查看下方数学推导）
- 因为小明和小亮总会上完整两套补习计划（自己的和对方的），所以只要有相同的补习班，就一定能在第一个相同的课上碰上。
-
-
没公共课怎么办：
如果两个计划完全不重合，他们最终都会上完对方的课，开心回家（return p1）。
复杂度
-
时间复杂度：O(n）
-
空间复杂度：O(1)
- 只有两个心机boy（两个指针变量），不多花内存。
记忆秘诀
心机boy上课策略：上自己的补习计划 -> 偷偷上对方的补习计划 -> 碰面社死翻车。
翻车条件：他们最终会在第一个共同的补习班上撞个正着，这就是“第一个公共节点”。如果没公共课，那就各回各家、各找各妈。
补充：数学推导
设定
指针P1和P2的移动逻辑：
- 指针P1：
- 指针P2：
总结： 两指针各自遍历两条链表的总路径相等：
LAbefore + LC + LBbefore + LC = LBbefore + LC + LAbefore + LC
相遇条件：
直观解释
python%E4%BB%A3%E7%A0%81">python代码
python"># class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#
class Solution:def FindFirstCommonNode(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:if not pHead1 or not pHead2:# 如果有一个补习计划为空，则不可能有共同补习班return None # 如果其中一个链表为空，则没有公共节点p1 = pHead1 # 小明从pHead1开始p2 = pHead2 # 小亮从pHead2开始# 当小明和小亮没有碰面时，继续上课# 遍历两个链表，直到找到公共节点或者都为Nonewhile p1 != p2:# 如果p1走到末尾，切换到pHead2；否则继续走# 如果小明的课上完了，就转去上小亮的，否则继续上自己的# p1 = p1.next if p1 else pHead2（简写）if p1: # 如果 p1 不是空p1 = p1.next # 继续往下走else: # 如果 p1 是空p1 = pHead2 # 切换到链表2的头节点# 如果p2走到末尾，切换到pHead1；否则继续走# 如果小红的课上完了，就转去上小明，否则继续上自己的# p2 = p2.next if p2 else pHead1（简写）if p2: # 如果 p2 不是空p2 = p2.next # 继续往下走else: # 如果 p2 是空p2 = pHead1 # 切换到链表1的头节点# 相遇点即为第一个公共节点，或者如果没有公共节点则为None# 碰面的补习班（公共节点），或者没有碰面（返回 None）return p1* 欢迎大家探讨新思路，能够更好的理解和记忆
![[毕业设计]最全计算机专业毕业设计选题推荐汇总（源码+论文）](https://i-blog.csdnimg.cn/blog_migrate/3ef1061399a1bf5e8d80c7516b0c8f4a.png)
