Description
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀空间。例如，“loading”和“being”的存储映像如下图所示：
设str1和str2分别指向两个单词所在单链表的头结点，请实现一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置的结点，输出该结点对应的字符（如图中的字符i）。
Input
多组数据，每组数据有三行，第一行为链表str1和str2的长度n和m，第二行为链表str1的n个元素，第三行为链表str2的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。
Output
对于每组数据输出一行，为共同后缀的起始位置结点对应的字符。
Sample Input
75
loa d i n g
bei n g
79
flu e n c y
fre q u e n c y
00
Sample Output
i
u
参考程序（C语言实现）
#include <stdio.h>
#include <stdlib.h>
#define ROOM sizeof(struct ListNode)
#define LEN 200
struct ListNode
{
char letter;
struct ListNode *next;
};
struct ListNode* CreateList(int n)
{
struct ListNode *head,*p1,*p2;
char word[LEN];
int i;
head=(struct ListNode*)malloc(ROOM);
head->next=NULL;
p2=head;
gets(word);
for(i=0;i<=2*(n-1);i+=2)
{
p1=(struct ListNode*)malloc(ROOM);
p1->letter=word[i];
p1->next=NULL;
p2->next=p1;
p2=p1;
}
return head;
}
int main()
{
int n,m;
while(1)
{
scanf("%d%d",&n,&m);
if(n==0&&m==0)
{
break;
}
else
{
struct ListNode *head1,*head2,*p1,*p2;
int i,flag=0;
char tag;
getchar();
head1=CreateList(n);
head2=CreateList(m);
p1=head1->next,p2=head2->next;
if(n>m)
{
for(i=1;i<=n-m;i++)
{
p1=p1->next;
}
}
else if(n<m)
{
for(i=1;i<=m-n;i++)
{
p2=p2->next;
}
}
while(p1&&p2)
{
if(p1->letter==p2->letter)
{
if(!flag)
{
tag=p1->letter;
flag=1;
}
}
else
{
flag=0;
}
p1=p1->next;
p2=p2->next;
}
printf("%c\n",tag);
}
}
return 0;
}
//by jialChen
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: