Java刪除值相同的多余結(jié)點(diǎn)的算法是什么

發(fā)布時(shí)間：2021-12-23 17:27:51 來(lái)源：億速云閱讀：135 作者：iii 欄目：大數(shù)據(jù)

本篇內(nèi)容介紹了“Java刪除值相同的多余結(jié)點(diǎn)的算法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

這是一道算法題，寫(xiě)算法題最恨沒(méi)有圖解，懂的人不需要看你的文章，不懂的你再怎么講解也沒(méi)有幾張圖解來(lái)得簡(jiǎn)單易懂，下面來(lái)分析一下這道題。

我暫時(shí)還沒(méi)有更好的解決方案，雖然有一個(gè)辦法解決，但是時(shí)間復(fù)雜度有點(diǎn)高，先看看我的思路吧。

Java刪除值相同的多余結(jié)點(diǎn)的算法是什么 — 在這里插入圖片描述

這是一個(gè)無(wú)序的單鏈表，我們采用一種最笨的辦法，先指向首元結(jié)點(diǎn)，其元素值為2，再遍歷該結(jié)點(diǎn)后的所有結(jié)點(diǎn)，若有結(jié)點(diǎn)元素值與其相同，則刪除；全部遍歷完成后，我們?cè)僦赶虻诙€(gè)結(jié)點(diǎn)，再進(jìn)行同樣的操作。

看圖解：

這里有兩個(gè)指針變量p、q，均指向單鏈表的首元結(jié)點(diǎn)，我們先不移動(dòng)指針p，而是讓指針q去遍歷之后的所有結(jié)點(diǎn)。

先讓指針p指向的結(jié)點(diǎn)與后一個(gè)結(jié)點(diǎn)比較，這里為了操作方便，我們暫且先不移動(dòng)指針q，而是這樣進(jìn)行比較： p -> data == q -> next -> data；若不相等，則讓q指向下一個(gè)結(jié)點(diǎn)： p = p->next；若相等，則應(yīng)該先保存下一個(gè)結(jié)點(diǎn)： r = q -> next，然后讓q指針指向下一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)： q = r -> next，并釋放r指向的結(jié)點(diǎn)內(nèi)存。

這樣就成功刪除了一個(gè)與首元結(jié)點(diǎn)重復(fù)的結(jié)點(diǎn)，接下來(lái)以同樣的方式繼續(xù)比較，直到整個(gè)單鏈表都遍歷完畢，此時(shí)單鏈表中已無(wú)與首元結(jié)點(diǎn)重復(fù)的結(jié)點(diǎn)；然后我們就要修改p指針的指向，讓其指向首元結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，再讓q指向其下一個(gè)結(jié)點(diǎn)，繼續(xù)遍歷，將單鏈表中與第二個(gè)結(jié)點(diǎn)重復(fù)的所有結(jié)點(diǎn)刪除。以此類(lèi)推，直至指針p也遍歷完了整個(gè)單鏈表，則算法結(jié)束。

剛才我們已經(jīng)刪除了一個(gè)結(jié)點(diǎn)，那么接下來(lái)p應(yīng)該指向下一個(gè)結(jié)點(diǎn)了：

此時(shí)讓指針p指向的結(jié)點(diǎn)與下一個(gè)結(jié)點(diǎn)的元素值比較，發(fā)現(xiàn)不相等，那么讓q直接指向下一個(gè)結(jié)點(diǎn)即可： q = q -> next。

繼續(xù)讓q指向的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)與p指向的結(jié)點(diǎn)的元素值比較，發(fā)現(xiàn)不相等，此時(shí)繼續(xù)移動(dòng)q，移動(dòng)過(guò)后q的指針域?yàn)镹ULL，說(shuō)明遍歷結(jié)束，此時(shí)應(yīng)該移動(dòng)指針p。

通過(guò)比較發(fā)現(xiàn)，下一個(gè)結(jié)點(diǎn)的元素值與其相等，接下來(lái)就刪除下一個(gè)結(jié)點(diǎn)即可：

此時(shí)p的指針域也為NULL，算法結(jié)束。

代碼如下：

LinkList DeleteRepeat(LinkList l){
    LinkList p,q,r;
    p = l->next;
    while(p != NULL){
        q = p;
        while(q->next != NULL){
            if(p->data == q->next->data){
                r = q->next;
                q = r->next;
                free(r);    
            }else{
                q = q->next;
            }
        }
        p = p->next;
    }
    return l;
}

“Java刪除值相同的多余結(jié)點(diǎn)的算法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

向AI問(wèn)一下細(xì)節(jié)

Java刪除值相同的多余結(jié)點(diǎn)的算法是什么

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽