目录：
目的
思路
复杂度
记忆秘诀
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）
- 两个心机boy的上课过程相当于遍历两个链表，每个节点最多访问两次，总共为 O(m+n)（m 和 n是链表的长度）即O(n)。
-
空间复杂度：O(1)
- 只有两个心机boy（两个指针变量），不多花内存。
记忆秘诀
心机boy上课策略：上自己的补习计划 -> 偷偷上对方的补习计划 -> 碰面社死翻车。
翻车条件：他们最终会在第一个共同的补习班上撞个正着，这就是“第一个公共节点”。如果没公共课，那就各回各家、各找各妈。
补充：数学推导
设定
- 链表A长度为LA，链表B 长度为LB。
- 两链表公共部分长度为 LC（第一个公共节点到链表尾部的长度）。
- 非公共部分：
- 链表A的独占部分为 LAbefore = LA - LC。
- 链表B的独占部分为 LBbefore = LB - LC。
指针P1和P2的移动逻辑：
- 指针P1：
- 从链表 A的头节点出发，依次走完链表 A，然后切换到链表B。
- 总路径： LAbefore + LC + LBbefore + LC
- 指针P2：
- 从链表B的头节点出发，依次走完链表B，然后切换到链表A。
- 总路径： LBbefore + LC + LAbefore + LC
总结： 两指针各自遍历两条链表的总路径相等：
LAbefore + LC + LBbefore + LC = LBbefore + LC + LAbefore + LC
相遇条件：
-
当指针P1 和 P2交换链表后：
- P1进入链表B，P2进入链表A，
- 由于他们行走的总路径相同，必然会在公共部分 LC的起点（即第一个公共节点）相遇。
-
如果两个链表没有公共部分（即 LC=0），两指针最终会同时走到
None，也满足终止条件。
直观解释
- 两个指针通过在链表间“交叉跑”，平衡了两链表的长度差异。
- 当两指针的行走路径一致时，自然会在第一个公共节点 C相遇。
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* 欢迎大家探讨新思路，能够更好的理解和记忆
