数据结构习题24/12/24

这道题目可以考虑，如果前缀是一样的长度，那么只需要两个链表同时向后检索，直到找到一样的元素为止。所以应该先找到两个链表的长度，然后将较长的一个链表的多出来的前缀部分删掉，也就不去看这一部分。因为后缀都是一样的，所以长度的差异只可能来自前缀。
解决代码：

typedef struct Node{    char data;    struct Node *next;}SNode;int listlen(SNode *head){    int len=0;    while(head->next!=NULL){        len++;        head=head->next;    }    return len;}SNode* find_addr(SNode *str1,SNode *str2){    int m,n;    m=listlen(str1);    n=listlen(str2);    SNode *p,*q;    for(p=str1;m>n;m--)        p=p->next;    for(q=str2;n>m;n--)        q=q->next;    while (p->next!=NULL&&p->next!=q->next)    {        p=p->next;        q=q->next;    }    return p->next;    }

这个问题关键在于每次都需要回到链表的最后进行操作，所以不妨把整个两边平分为前后两部分，将后面整个逆转，变成两个链表。再将后面部分的链表依次插入到前面部分的链表中。

void change_list(SNode *h){    SNode *p,*q,*r,*s;    p=q=h;    while(q->next!=NULL){        p=p->next;        q=q->next;        if(q->next!=null) q=q->next;    }    q=p->next;    p->next=NULL;    while (q!=NULL)    {        r=q->next;        q->next=p->next;        p->next=q;        q=r;    }    s=h->next;    q=p->next;    p->next=NULL;    while (q!=NULL)    {        r=q->next;        q->next=s->next;        s->next=q;        s=q->next;        q=r;    }        }

本文由博客一文多发平台 OpenWrite 发布！