题目

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，"loading" 和 "being" 的存储映像如下所示：

list str1: l, o, a, d
list str2: b, e
shared: i, n, g
pointer p: shared:0

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data | next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如上图中字符 i 所在结点的位置 p）。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度。

解析

(1) 设计思想

答案：先量出两条链表的长度 m、n（不含头结点）；让较长那条的指针先走 |m − n| 步；然后两个指针同步前进，第一个让 p == q 成立的位置就是共同后缀的起始点。

为什么这样能找到共同后缀的起点？

题面说"共同后缀共享存储"——即共同后缀的所有结点是同一段内存地址，不是值相同的两段独立链表。所以判等用 p == q（指针相同）而不是 p->data == q->data。

由于两条链表共享尾部，从尾部往前看，后缀长度一定相同。如果两条链表的非共享前缀部分长度分别是 、（满足 、， 为共同后缀长），那么：

• 让较长一方先走 步，两个指针就距离尾部一样远；
• 同步前进，从前缀进入共同后缀的那一刻，两指针正好都跨入第一个共享结点——p == q 立即成立。

关键洞察：本题的关键不是"找最长公共子串"——共享是物理共享，而非数值相同。所以不需要任何字符比较，只比指针。

(2) 代码实现

typedef struct ListNode {
    char data;
    struct ListNode *next;
} ListNode;

ListNode* findCommonSuffix(ListNode *str1, ListNode *str2) {
    int m = 0, n = 0;

    // ① 量两条链的长度（不含头结点）
    for (ListNode *p = str1->next; p != NULL; p = p->next) m++;
    for (ListNode *p = str2->next; p != NULL; p = p->next) n++;

    // ② 让较长的那条先走 |m - n| 步，使两指针距尾部相同
    ListNode *p = str1->next;
    ListNode *q = str2->next;
    while (m > n) { p = p->next; m--; }
    while (n > m) { q = q->next; n--; }

    // ③ 同步前进，第一个 p == q 的位置就是共同后缀起点
    while (p != NULL && q != NULL && p != q) {
        p = p->next;
        q = q->next;
    }

    return p;     // 若无共同后缀，最终 p、q 都走到 NULL，返回 NULL
}

关键点说明：

• 判等用指针 p != q，不是 p->data != q->data：题目要求"找共享存储的起始结点"，必须按地址判定。值相同但地址不同的两个独立结点不算共同后缀。
• 量长度时跳过头结点：题面用"带头结点"的链表，遍历从 str1->next 开始。
• 不需要修改链表：本算法只读不写，原链表结构不变。
• 若两链表完全无共同后缀：最终 p 与 q 同步走到 NULL，循环退出时 p == q == NULL，返回 NULL（没有共同后缀）。

(3) 时间复杂度

• 时间复杂度 即 ：第一遍量长度 O(m+n)；第二遍同步前进最坏走完较长链表 O(max(m,n))。
• 空间复杂度 ：只用 m、n、p、q 几个标量。

编者注（生僻术语）：本题的"先对齐再齐步走"思想是单链表问题的常见模式——同样的技巧也用在「找两条链表的相交点」「找倒数第 k 个结点」等场景。考场中能写出这套模式就稳拿满分。