数据结构
2012-42
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。
设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 [data | next]，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度。
答案
（1）算法的基本设计思想
首先分别遍历两个链表，计算其数据结点个数 len1 和 len2 。然后使两个链表尾部对齐：让较长链表的指针先移动长度差值个结点，使两个指针到链表尾的距离相等。最后同步移动两个指针，直到它们指向同一个结点，该结点即为共同后缀的起始位置；若直至链表尾未相遇，则无共同后缀。
（2）算法的C语言描述
typedef struct LinkNode {
char data;
struct LinkNode *next;
} LinkNode;
// 计算数据结点个数
int Length(LinkNode *head) {
int len = 0;
LinkNode *p = head->next; // 跳过头结点
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
// 查找共同后缀起始结点
LinkNode* FindCommonLinkList(LinkNode *str1, LinkNode *str2) {
int len1 = Length(str1), len2 = Length(str2);
LinkNode *p = str1, *q = str2;
// 对齐：使p和q到尾的距离相等
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++)
p = p->next;
} else {
for (int i = 0; i < len2 - len1; i++)
q = q->next;
}
// 同步移动直到相遇
while (p != NULL && q != NULL && p != q) {
p = p->next;
q = q->next;
}
return p; // p即为共同起始结点（若无则为NULL）
}（3）时间复杂度
时间复杂度为 O(len1 + len2) ，其中 len1 和 len2 分别为两个链表的数据结点个数。