剑指offer48_两个链表的第一个公共节点

两个链表的第一个公共节点

---

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

数据范围

链表长度 $[1,30000]$。
保证两个链表不完全相同，即两链表的头结点不相同。

样例

给出两个链表如下所示：
A：        a1 → a2↘c1 → c2 → c3↗            
B:     b1 → b2 → b3输出第一个公共节点c1

---

算法思路（双指针 + 路径交换）

1. 核心思想：
   • 使用两个指针 p 和 q 分别遍历链表 A 和 B。
   • 当任一指针到达链表末尾时，将其重定向到另一链表的头节点。
   • 若两链表有公共节点，p 和 q 会在第二次遍历时相遇；若无公共节点，最终会同时到达 NULL。
2. 关键操作：
   • 路径交换：p 遍历完 A 后转向 B，q 遍历完 B 后转向 A，抵消两链表的长度差。
   • 终止条件：p == q 时返回当前节点（公共节点或 NULL）。
3. 正确性证明
   • 无公共节点：两指针最终同时指向 NULL（p 和 q 均遍历 m + n 次）。
   • 有公共节点：
     • 设 A 独有部分长度为 a，B 独有部分为 b，公共部分为 c。
     • p 的路径：a + c + b，q 的路径：b + c + a，路径长度相同，必在公共节点相遇。

维度	说明	公式
时间复杂度	两指针最多遍历 m + n 个节点（m 和 n 为两链表长度）。	$O(m+n)$
空间复杂度	仅使用两个指针，无额外空间。	$O(1)$

---

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {auto p = headA, q = headB;  // 初始化双指针while (p != q) {             // 未相遇时继续遍历p = p ? p->next : headB; // p走到尽头后转向headBq = q ? q->next : headA; // q走到尽头后转向headA}return p;  // 返回公共节点或NULL}
};

示例演示

链表结构：

• A: 1 → 2 → 3 ↘
• B: 4 → 5 ↗
• 公共部分：6 → 7

指针路径：

1. p: 1 → 2 → 3 → 6 → 7
2. q: 4 → 5 → 6 → 7
   相遇点：节点 6（第一个公共节点）

---

**变种与扩展 **

1. 哈希表法：
   • 遍历链表 A 并存储节点到哈希表，再遍历 B 检查是否存在。
   • 时间复杂度：$O(m+n)$，空间复杂度：$O(m)$ 或 $O(n)$。
2. 长度差法：
   • 先计算两链表长度差 d，长链表指针先走 d 步，再同步遍历。
   • 时间复杂度：$O(m+n)$，空间复杂度：$O(1)$。
3. 环形链表检测：
   • 若允许修改链表，可将 B 的尾节点指向 A 的头，转化为环形链表入口问题（需恢复原结构）。