相交链表题解与详细分析

代码详解

第一部分：计算链表长度

struct ListNode *cur1 = headA;
struct ListNode *cur2 = headB;
int a = 0;
int b = 0;
// 计算链表 A 的长度
while(cur1) {
    a++;
    cur1 = cur1->next;
}
// 计算链表 B 的长度
while(cur2) {
    b++;
    cur2 = cur2->next;
}

• 使用两个指针分别遍历两个链表
• 计数器 a 和 b 分别记录链表 A 和链表 B 的长度

第二部分：对齐起点

cur1 = headA;
cur2 = headB;
int c = 0;
if(a > b) {
    c = a - b;
    while(c--) {
        cur1 = cur1->next;
    }
} else {
    c = b - a;
    while(c--) {
        cur2 = cur2->next;
    }
}

• 重置指针到链表头部
• 计算长度差值 c
• 让长链表的指针先移动 c 步，使两个指针后的剩余长度相等

第三部分：寻找相交节点

while(cur1) {
    if(cur1 == cur2) {
        return cur1;
    }
    cur1 = cur1->next;
    cur2 = cur2->next;
}
return NULL;

• 两个指针同时移动
• 比较节点地址是否相同（注意：是比较节点本身，不是节点值）
• 找到相同节点则返回，否则返回 NULL

执行过程可视化

以题目示例为例：

链表 A: a1 → a2 → c1 → c2 → c3
链表 B: b1 → b2 → b3 → c1 → c2 → c3

执行步骤：

1. 计算长度：
   • 链表 A 长度：5
   • 链表 B 长度：6
2. 对齐起点：
   • 长度差：1
   • 链表 B 指针先移动 1 步：b2 → b3 → c1 → c2 → c3
3. 同时遍历：
   • A: a1 → a2 → c1 → c2 → c3
   • B: b2 → b3 → c1 → c2 → c3
   • 在节点 c1 处相遇，返回 c1

优化方案：双指针法

还有一种更巧妙的方法，不需要计算链表长度：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) return NULL;
    struct ListNode *pA = headA;
    struct ListNode *pB = headB;
    while (pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return pA;
}

原理：

• 两个指针分别遍历两个链表
• 当指针到达链表末尾时，切换到另一个链表的头部
• 如果两个链表相交，指针会在相交点相遇
• 如果不相交，指针会同时到达 NULL

复杂度分析

长度差法

• 时间复杂度：O(m+n)，其中 m 和 n 分别是两个链表的长度
• 空间复杂度：O(1)，只使用常数级别的额外空间

双指针法

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)

关键点总结

1. 比较节点地址：注意是比较节点本身（指针地址），不是节点值
2. 链表无环：题目保证链表无环，简化了问题
3. 保持原始结构：算法不应该修改链表结构
4. 边界情况：处理空链表的情况

测试用例考虑

1. 不相交的链表：返回 NULL
2. 完全相同的链表：返回头节点
3. 一个链表是另一个的子集：返回较长链表的头部
4. 在中间节点相交：返回相交节点
5. 空链表：返回 NULL

应用场景

这种链表相交问题在实际开发中有多种应用：

1. 内存管理：检测两个数据结构是否共享内存区域
2. 图算法：在树或图中寻找公共节点
3. 版本控制系统：寻找代码分支的合并点
4. 数据库查询：优化连接查询的执行计划

总结

寻找相交链表节点是一个经典的链表问题，掌握两种解法都很重要：

1. 长度差法：思路直观，容易理解和实现
2. 双指针法：代码简洁，不需要计算长度

关键技巧：

• 利用相交后部分长度相同的特性
• 通过对齐起点来简化比较过程
• 注意指针操作和边界条件处理

这道题考察了对链表结构的理解和双指针技巧的应用，是面试中常见的问题之一。