Appearance
2012·42 共同后缀起点：从双层枚举到先对齐再齐步走
本文属于「从暴力解到最优解」专题。这道题真正的分水岭在动笔之前——先想明白「共享是物理共享，判等要用指针」。这一步想歪成字符比较，写得再快也是错的；想对了之后，暴力解只是慢，正确性的主体分照样在手。
题目
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，"loading" 和 "being" 的存储映像如下所示：
str1 ─→ l → o → a → d ─┐
├─→ i → n → g → NULL
str2 ─→ b → e ─────────┘
↑
p设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data | next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如上图中字符 i 所在结点的位置 p）。要求：
(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度。
总分 12 分。题面写了「时间上尽可能高效」——最优性分存在，判据是时间复杂度。
先立地基：判等用指针
写任何一版代码之前，必须把题意读透：「共享后缀存储空间」意味着共同后缀的结点是同一段内存——str1 走到 i 结点和 str2 走到 i 结点，走到的是同一个地址。所以「p 和 q 是不是同一个结点」要用 p == q 判断，而不是 p->data == q->data。
反例：两个单词各自独立存储，哪怕末尾若干个字符的值恰好相同，那也是两段地址无关的结点，不构成本题的「共同后缀」。用字符比较会把这种情况误判成共享——这是本题第一大丢分点，而且丢的是正确性的分，暴力解最优解都救不回来。
好消息是：判等想对之后，这道题一次字符比较都不需要做。
第一步：把暴力解写对
共享有个结构性质：一旦进入共享段就不会再分开——共享结点的 next 也是共享的。所以从前往后扫 str1，第一个同时出现在 str2 上的结点，就是共同后缀的起点。
暴力解由此成型：枚举 str1 的每个结点 p，到 str2 里从头找一遍，看有没有哪个 q 和 p 是同一个结点；第一个命中的 p 就是答案。
c
typedef struct ListNode {
char data;
struct ListNode *next;
} ListNode;
ListNode* findCommonSuffix(ListNode *str1, ListNode *str2) {
// 枚举 str1 的每个结点（跳过头结点）
for (ListNode *p = str1->next; p != NULL; p = p->next) {
// 到 str2 里从头找 p——判等用指针，不比 data
for (ListNode *q = str2->next; q != NULL; q = q->next) {
if (p == q) return p; // 第一个共享结点即共同后缀起点
}
}
return NULL; // 无共同后缀
}拿题面的例子走一遍：p 依次取 l、o、a、d，每次把 str2 的 b、e、i、n、g 扫一遍都不命中；p 走到 i 时，str2 扫到第三个结点命中（同一个地址），返回 i 结点 ✓。两条链完全独立时双层循环走完返回 NULL ✓。
复杂度：设两链长度（不含头结点）为 m、n，最坏情况下 str2 被完整扫 m 遍，时间
它值多少分
按正确性/最优性两个维度（详见总纲）：
- 正确性：设计思想能正确找到共同后缀起点、抓住了「物理共享、指针判等」这个关键、无共同后缀时返回 NULL——正确性维度的主体分拿得到。
- 最优性：题面要求「时间上尽可能高效」，标答是线性
；双层枚举 距离线性有真实差距，最优性档拿不到。
第 (3) 问复杂度照实写
暴力解的浪费在哪
用总纲的「找浪费三问」审一遍：
**有没有重复扫描？——有，很严重。**str2 被完整扫了 m 遍，每一遍只回答「p 在不在 str2 上」这一个 bit 的问题，扫完就扔，下一个 p 又从头来。
**有没有放着性质不用？——有，这才是关键。**共享后缀有个几何性质：共同后缀的每个结点，到两条链尾的距离是相同的（尾巴是同一条）。反过来说，两个「距离各自链尾一样远」的位置，要么同时在共享段里，要么同时不在。双层枚举完全没用这个性质——它拿 str1 距尾很远的结点去和 str2 距尾很近的结点比，这些比较注定不会命中，全是无用功。
对策：只比「距尾等远」的结点对。让两个指针先站到距尾一样远的位置，再齐步走，每对位置只比一次——比较次数从
智慧化改造：先对齐，再齐步走
「距尾等远」不需要从尾往前量（单链表也做不到），从头量就行：长度为 m 的链上，距尾 d 的结点就是从头走 m − d 步的位置。所以：
- 先各扫一遍，量出两链长度 m、n（不含头结点）；
- 让较长那条的指针先走 |m − n| 步——之后两个指针距各自链尾一样远；
- 两指针同步前进，第一个
p == q成立的位置就是共同后缀起点。
原理再精确一点：设共同后缀长 L、两链非共享前缀长 a、b，则 m = a + L、n = b + L，|m − n| = |a − b|。较长方先走掉这个差值后，两指针同步从各自前缀走向共享段，跨入第一个共享结点的时刻相同——p == q 在起点处立即成立。
c
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
}复杂度：量长度
从双层枚举升级过来，四个细节决定这 12 分能拿多满：
- 判等仍然是
p == q。升级改的是扫描方式，不是判等方式——换成同步前进后拿 data 比较照样是错的，这一点两版通用。 - 对齐方向别写反。m > n 时该走的是 p（str1 那条长），写反了会让短链的指针提前越界。两个 while 各管一个方向，只会执行其中一个。
- 同步循环的退出条件是三件套：
p != NULL && q != NULL && p != q。漏掉p != q会从起点径直走过头一路到 NULL；把&&写成||会提前停。 - 无共同后缀不用特判。两指针同步走到尾，
p == q == NULL让循环自然退出，返回的 p 恰好就是 NULL——代码里一行特判都不需要，但设计思想里要说清这一点。
两版对照跑一遍
可视化里用数字代替字符：str1 为 1 → 2 → 3 → 4 → 7 → 8 → 9，str2 为 5 → 6 接入同一段 7 → 8 → 9——驱动代码先分别 buildList，再把 str2 尾结点的 next 指向 str1 的第 5 个结点，构造出真实的物理共享，答案是值为 7 的那个共享结点。先看双层枚举版——注意外层每前进一步，内层都从头扫一遍：
再看先对齐再齐步走版——str1 的指针先走掉长度差 2，之后两个指针各自只走一遍：
演示为不带头结点的 JavaScript 等价版本，用数字代替字符、返回共同后缀起始结点；考卷上请按题面用带头结点写法（上文 C 代码）。
等价方法与升级空间
- 哈希集合法：把 str1 全部结点的地址放进集合，再扫 str2 找第一个命中。时间同为线性
，但辅助集合占 空间——拿正确性分，最优性上不如 空间的对齐法。 - 「先对齐再齐步走」是可迁移的模式：找两条链表的相交点、找倒数第 k 个结点（2009·42 里 fast 提前 k 步本质就是一种对齐）都用同一套动作。把「让两个指针站到对称位置再同步走」练成肌肉记忆，这一片题就都通了。
下一步
- 在 OJ 上把两版代码都提交跑一遍：ds-2012-42 链表共同后缀
- 回到题库看这道题的完整解析与错因：真题库 · 数据结构