【数据结构与算法】相交链表求交点

相交链表检测算法详解

一、问题描述

1.1 题目要求

LeetCode 160. 相交链表
给定两个单链表的头节点headA和headB，请找出它们的第一个公共节点。如果两个链表没有交点，返回null。

关键约束：

公共节点是指内存地址相同的节点（非值相同）
链表长度可能不等（0 ≤ 节点数 ≤ 10^4）
节点值范围：[-100, 100]

1.2 典型场景

链表A：1 → 2 → 3↘5 → 6 → 7↗
链表B：   4 → 5 → 6 → 7

第一个公共节点为5（地址相同）

二、解题思路

2.1 方法对比

方法	时间复杂度	空间复杂度	适用场景
双循环对比	O(n²)	O(1)	小规模链表
双指针法	O(n)	O(1)	常规场景（推荐）
哈希表法	O(n)	O(n)	需要记录节点地址时使用

2.2 核心算法：双指针法

2.2.1 算法原理

长度对齐：先遍历两个链表获取长度差
差值步进：长链表指针先移动差值步数
同步遍历：双指针同步移动，首次相遇点即为交点

2.2.2 关键步骤

1. 计算链表A长度：countA
2. 计算链表B长度：countB
3. 计算长度差：diff = |countA - countB|
4. 长链表指针先移动diff步
5. 双指针同步移动，比较节点地址

2.2.3 正确性证明

设公共部分长度为C，非公共部分长度分别为L1和L2
长链表指针先走L1+C+diff = L2+C步（消除长度差）
此时双指针剩余步数相同，必然在公共起点相遇

三、源代码实现

3.1 双循环对比法（暴力解法）

/*** 暴力解法：双层循环遍历* 时间复杂度O(n²)，空间复杂度O(1)*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode *pA = headA;// 遍历链表A的每个节点while (pA != NULL) {ListNode *pB = headB;// 遍历链表B的每个节点while (pB != NULL) {// 比较节点地址（关键判断）if (pA == pB) return pA;pB = pB->next;}pA = pA->next;}return NULL;
}

3.2 双指针法（优化解法）

/*** 优化解法：双指针法* 时间复杂度O(n)，空间复杂度O(1)*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {// 计算链表长度int lenA = getLength(headA), lenB = getLength(headB);// 初始化指针ListNode *pLong = lenA > lenB ? headA : headB;ListNode *pShort = lenA > lenB ? headB : headA;// 长链表先走差值步int diff = abs(lenA - lenB);while (diff--) pLong = pLong->next;// 同步遍历比较while (pLong != NULL && pShort != NULL) {if (pLong == pShort) return pLong;pLong = pLong->next;pShort = pShort->next;}return NULL;
}// 辅助函数：计算链表长度
int getLength(struct ListNode *head) {int count = 0;while (head != NULL) {count++;head = head->next;}return count;
}

四、算法验证

4.1 测试用例

测试场景	输入示例	预期输出
有公共节点	A:1→2→3, B:4→5, 公共部分5→6	节点5
无公共节点	A:1→2, B:3→4	NULL
头节点相交	A:5→6, B:5→6	节点5
尾节点相交	A:1→2→3, B:4→5→3	节点3
空链表	A:NULL, B:1→2	NULL