问题
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可以共享相同的后缀存储空间。例如“loading”和“beging”的存储映像如下图所示。
设str1和str2分别指向两个单词所在的单链表的头结点，链表结点结构为（data，next）。请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表的共同后缀的起始位置（如上图中字符i所在结点的位置p）
分析
求出str1和str2的长度，如果长度相等，则单词长度相同，否则，移动指针使两个单词的词尾对齐，然后找出公共部分的起始位置（并不是第一个字符相等的位置就是所求位置）。
和王道的代码不一样，正确与否自己想想。
代码
LinkList findSame(LinkList str1, LinkList str2) {///找公共后缀int str1Num = getLength(str1);///求str1的长度int str2Num = getLength(str2);///求str2的长度LNode *p, *q;///移动p、q指针，使单词的尾对齐if(str1Num == str2Num) {p = str1 -> next;q = str2 -> next;}else if(str1Num < str2Num) {p = str1 -> next;q = str2 -> next;int i = 0;for(int i = 0; i < str2Num - str1Num; i++) {q = q -> next;}}else {p = str1 -> next;q = str2 -> next;int i = 0;for(int i = 0; i < str1Num - str2Num; i++) {p = p -> next;}}///找公共后缀while(p) {int temp;if(p -> data != q -> data) {///当前节点值不相等，向后找p = p -> next;q = q -> next;} else {///当前节点值相等，则向后遍历，之后的每一个节点值都相等，此节点///才是所求，一个结点值不相等，就不是所求LNode *p1 = p -> next;LNode *q1 = q -> next;while(p1) {temp = 1;if(p1 -> data != q1 -> data) {temp = 0;break;}p1 = p1 -> next;q1 = q1 -> next;}if(temp == 1) {return p;}else {p = p1 -> next;q = q1 -> next;}}}
}
