AC213-找出两个单链表的共同后缀起始位置¶

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间。设 str1 和 str2 分别指向两个单词所在链表的头结点，请设计一个时间上尽可能高效的算法，找出这两个链表的共同后缀的起始位置。（2012 年统考题）

代码实现¶

C
// 函数 find：找出两个单链表的共同后缀起始位置
// 假设两个链表在某个位置开始共享相同的后缀
LinkList find(LinkList str1, LinkList str2) {
    // 初始化指针和长度计数器
    LinkList p = str1->next, q = str2->next; // p、q 分别指向两个链表的第一个数据节点
    int len1 = 0, len2 = 0; // len1、len2 分别记录两个链表的长度

    // 计算第一个链表的长度
    while (p != NULL) {
        p = p->next;
        len1++;
    }

    // 计算第二个链表的长度
    while (q != NULL) {
        q = q->next;
        len2++;
    }

    // 重新将指针指向链表的起始位置
    p = str1->next;
    q = str2->next;

    // 对齐两个链表的起始位置
    // 如果第一个链表更长，则将 p 指针向前移动 (len1 - len2) 个位置
    for (; len1 > len2; len1--) {
        p = p->next;
    }

    // 如果第二个链表更长，则将 q 指针向前移动 (len2 - len1) 个位置
    for (; len2 > len1; len2--) {
        q = q->next;
    }

    // 同步移动两个指针，寻找第一个相同的节点（即共同后缀的起始位置）
    while (p != NULL && q != NULL) {
        if (p == q) { // 比较指针地址，而不是节点数据
            return p; // 找到共同后缀的起始位置
        }
        p = p->next;
        q = q->next;
    }

    // 如果没有找到共同后缀，返回 NULL
    return NULL;
}

代码逻辑解析¶

1. 问题理解¶

两个单词链表可能共享相同的后缀部分
需要找到这个共享部分的起始位置
关键：比较的是节点的地址，不是节点的数据

2. 算法思路¶

这是一个经典的"寻找两个链表相交点"问题，采用"对齐后同步移动"的策略：

步骤1：计算长度 - 分别遍历两个链表，计算各自的长度

步骤2：对齐起点 - 让较长链表的指针先走 |len1 - len2| 步 - 使得两个指针距离各自链表尾部的距离相等

步骤3：同步移动 - 两个指针同时向前移动 - 当遇到第一个相同地址的节点时，即为共同后缀的起始位置

3. 关键点说明¶

地址比较：if (p == q) 比较的是指针地址，不是节点内容
共享后缀：意味着从某个节点开始，两个链表完全重合
对齐策略：通过让长链表先走，确保同步移动时能同时到达交点

时间复杂度分析¶

第一次遍历：O(m) + O(n)，其中 m、n 分别为两个链表的长度
对齐操作：O(|m - n|)
同步移动：O(min(m, n))
总体复杂度：O(max(m, n))

空间复杂度分析¶

只使用了常量级别的额外变量（p, q, len1, len2）
空间复杂度为 O(1)

较难理解部分的说明¶

为什么比较地址而不是数据？¶

C
// 错误的理解：比较数据内容
if (p->data == q->data) // ❌ 可能有多个节点数据相同

// 正确的理解：比较节点地址  
if (p == q) // ✅ 只有共享节点的地址才相同

当两个链表共享后缀时，它们实际上指向同一个内存地址的节点序列。

图解说明¶

假设两个链表：

Text Only
1 2 3 4	`str1: A -> B -> C -> D -> E -> F -> NULL ↑ \| str2: X -> Y -> Z -> D -> E -> F -> NULL`

步骤演示：

Text Only

步骤1：计算长度
str1长度 = 6 (A,B,C,D,E,F)
str2长度 = 6 (X,Y,Z,D,E,F)

步骤2：对齐（长度相等，无需对齐）
p -> A
q -> X

步骤3：同步移动
比较 A ≠ X，移动 p->B, q->Y
比较 B ≠ Y，移动 p->C, q->Z  
比较 C ≠ Z，移动 p->D, q->D
比较 D == D，找到交点！返回 D 的地址

再看一个长度不同的例子：

Text Only
1 2 3 4	`str1: A -> B -> C -> D -> E -> NULL (长度5) ↑ \| str2: X -> Y -> C -> D -> E -> NULL (长度5)`

Text Only

步骤1：计算长度
len1 = 5, len2 = 5

步骤2：对齐
由于长度相等，无需对齐

步骤3：同步移动
p->A, q->X: A≠X, 移动
p->B, q->Y: B≠Y, 移动  
p->C, q->C: C==C, 找到交点！

如果长度不同：

Text Only
1 2 3 4	`str1: A -> B -> C -> D -> E -> F -> G -> NULL (长度7) ↑ \| str2: X -> Y -> Z -> D -> E -> F -> G -> NULL (长度7)`

Text Only

步骤1：len1=7, len2=7
步骤2：对齐（实际代码中的 for 循环）
str1 比 str2 长 2 个节点，所以 p 先走 2 步
p 从 A 开始，走 2 步后指向 C
现在 p->C, q->X，距离尾部都是 5 个节点
步骤3：同步移动找到交点 D

延伸知识点¶

1. 其他解法¶

方法二：双指针技巧（无需计算长度）

C
LinkList find_intersection(LinkList headA, LinkList headB) {
    LinkList p = headA, q = headB;
    while (p != q) {
        p = (p == NULL) ? headB : p->next;
        q = (q == NULL) ? headA : q->next;
    }
    return p;
}

方法三：使用栈

C
1 2	`// 将两个链表分别压入栈中，然后同时弹出比较 // 时间复杂度 O(m+n)，空间复杂度 O(m+n)`

2. 实际应用场景¶

内存管理：检测循环引用
版本控制：寻找两个分支的共同祖先
图论算法：寻找两条路径的交点
数据库：检测循环外键引用

3. 相关问题变体¶

变体1：判断两个链表是否相交

C
bool isIntersect(LinkList headA, LinkList headB) {
    if (!headA || !headB) return false;

    LinkList p = headA, q = headB;
    while (p->next) p = p->next;
    while (q->next) q = q->next;

    return p == q; // 比较尾节点地址
}

变体2：计算交点到尾部的距离

C
int getTailDistance(LinkList intersection) {
    int count = 0;
    while (intersection) {
        count++;
        intersection = intersection->next;
    }
    return count;
}

4. 边界情况处理¶

C
LinkList find_robust(LinkList str1, LinkList str2) {
    // 边界检查
    if (!str1 || !str2 || !str1->next || !str2->next) {
        return NULL;
    }

    // 原算法...
    // 添加适当的 NULL 检查
}

这种方法体现了算法设计中的数学对称性思想：通过让较长链表先走，创造出对称的条件，然后同步移动找到交点。这是解决链表相交问题的经典高效算法。