谷歌上怎样做网站,门户网站的盈利模式,积分商城,六安市城市建设档案馆网站假定采用带头结点的单链表保存单词#xff0c;当两个单词有相同的后缀时#xff0c;则可共享相同的后缀存储空间#xff0c;例如#xff0c;’loading’和’being’的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点#xff0c;链表结点结构为 data…假定采用带头结点的单链表保存单词当两个单词有相同的后缀时则可共享相同的后缀存储空间例如’loading’和’being’的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点链表结点结构为 datanext 请设计一个时间上尽可能高效的算法找出由str1和str2所指向两个链表共同后缀的起始位置如图中字符i所在的结点位置p。
方法一暴力
思想外层循环遍历str1内存循环遍历str2遍历过程中比较是否相等。
代码
typedf char ElemType;
typedf struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList;
LinkList getsameNode(LinkList L1,LinkList L2){L1L1-next;while(L1!NULL){//外层循环L1 LNode *pL2-next;while(p!NULL){//内存循环L2 if(L1p){return L1;}pp-next;}L1L1-next;}//没找到 return NULL;
}
时间复杂度Olen1len2空间复杂度O1
方法二让较长的链表先移动直到两个链表长度一样时进行同时移动。
思想分别求两个链表长度。然后对较长的那个链表先进行遍历直到两个链表相同时进行同时遍历直到找到公共结点为止。
代码
int length(LinkList L){//计算链表长度 int len0;LL-next;while(L!NULL){len;LL-next;}return len;
}
LinkList getsameNode(LinkList L1,LinkList L2){//计算链表长度int len1length(L1);int len2length(L2);for(pL1;len1len2;len1--){//链表1更长时 pp-next;}for(qL2;len2len1;len2--){//链表2更长时 qq-next;}while(p-next!NULL p-next!q-next){//此时两个链表一样长进行差查第一个公共节点 pp-next;qq-next;}return p-next;//返回查找到的结点
}
时间复杂度Olen1len2空间复杂度O1
