數據結構習題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 發佈！