一位小伙伴來問一道谷歌的筆試題表制，關(guān)于單鏈表操作的健爬，問到底有多少種解決方案，今天我們就來聊聊么介。
題目的大致意思是：
假設(shè)存在一個(gè)無序單鏈表娜遵，將重復(fù)結(jié)點(diǎn)去除后，并保原順序壤短。去重前：1→3→1→5→5→7去重后：1→3→5→7
順序刪除
通過雙重循環(huán)直接在鏈表上執(zhí)行刪除操作设拟。外層循環(huán)用一個(gè)指針從第一個(gè)結(jié)點(diǎn)開始遍歷整個(gè)鏈表，然后內(nèi)層循環(huán)用另外一個(gè)指針遍歷其余結(jié)點(diǎn)久脯，將與外層循環(huán)遍歷到的指針?biāo)附Y(jié)點(diǎn)的數(shù)據(jù)域相同的結(jié)點(diǎn)刪除纳胧，如下圖所示。
假設(shè)外層循環(huán)從outerCur開始遍歷帘撰，當(dāng)內(nèi)層循環(huán)指針innerCur遍歷到上圖實(shí)線所示的位置（outerCur.data==innerCur.data）時(shí)跑慕，此時(shí)需要把innerCur指向的結(jié)點(diǎn)刪除。
具體步驟如下：
- 用tmp記錄待刪除的結(jié)點(diǎn)的地址摧找。
- 為了能夠在刪除tmp結(jié)點(diǎn)后繼續(xù)遍歷鏈表中其余的結(jié)點(diǎn)核行，使innerCur指針指向它的后繼結(jié)點(diǎn)：innerCur=innerCur.next。
- 從鏈表中刪除tmp結(jié)點(diǎn)蹬耘。
實(shí)現(xiàn)代碼如下：
[圖片上傳失敗...(image-327f7f-1614062950016)]
[圖片上傳失敗...(image-9c0473-1614062950016)]
[圖片上傳失敗...(image-465005-1614062950016)]
運(yùn)行結(jié)果：
[圖片上傳失敗...(image-3c179c-1614062950016)]
算法性能分析
由于這種方法采用雙重循環(huán)對(duì)鏈表進(jìn)行遍歷芝雪，因此，時(shí)間復(fù)雜度為O（N^2）综苔。其中绵脯，N為鏈表的長度。在遍歷鏈表的過程中休里，使用了常量個(gè)額外的指針變量來保存當(dāng)前遍歷的結(jié)點(diǎn)蛆挫、前驅(qū)結(jié)點(diǎn)和被刪除的結(jié)點(diǎn)，因此妙黍，空間復(fù)雜度為O（1）悴侵。
遞歸法
主要思路為：對(duì)于結(jié)點(diǎn)cur，首先遞歸地刪除以cur.next為首的子鏈表中重復(fù)的結(jié)點(diǎn)拭嫁，接著從以cur.next為首的子鏈表中找出與cur有著相同數(shù)據(jù)域的結(jié)點(diǎn)并刪除可免。
實(shí)現(xiàn)代碼如下：
[圖片上傳失敗...(image-ff77ce-1614062950016)]
[圖片上傳失敗...(image-6eb908-1614062950016)]
[圖片上傳失敗...(image-ba82a3-1614062950016)]
算法性能分析
這種方法與方法一類似，從本質(zhì)上而言做粤，由于這種方法需要對(duì)鏈表進(jìn)行雙重遍歷浇借，因此，時(shí)間復(fù)雜度為O（N^2）怕品。其中妇垢，N為鏈表的長度。由于遞歸法會(huì)增加許多額外的函數(shù)調(diào)用，因此闯估，從理論上講灼舍，該方法效率比前面的方法低。
空間換時(shí)間
通常情況下涨薪，為了降低時(shí)間復(fù)雜度骑素，往往在條件允許的情況下，通過使用輔助空間實(shí)現(xiàn)刚夺。
具體而言献丑，主要思路如下盾戴。
- 建立一個(gè)HashSet盅视，HashSet中的內(nèi)容為已經(jīng)遍歷過的結(jié)點(diǎn)內(nèi)容，并將其初始化為空含懊。
- 從頭開始遍歷鏈表中的<typo id="typo-936" data-origin="所以" ignoretag="true">所以</typo>結(jié)點(diǎn)结借，存在以下兩種可能性：
- 如果結(jié)點(diǎn)內(nèi)容已經(jīng)在HashSet中，則刪除此結(jié)點(diǎn)卒茬，繼續(xù)向后遍歷船老。
- 如果結(jié)點(diǎn)內(nèi)容不在HashSet中，則保留此結(jié)點(diǎn)圃酵，將此結(jié)點(diǎn)內(nèi)容添加到HashSet中柳畔，繼續(xù)向后遍歷。
「引申：如何從有序鏈表中移除重復(fù)項(xiàng)郭赐？」
如鏈表：1,3薪韩、5、5捌锭、7俘陷、7、8观谦、9
去重后：1,3拉盾、5、7豁状、8捉偏、9
分析與解答
上述介紹的方法也適用于鏈表有序的情況，但是由于以上方法沒有充分利用到鏈表有序這個(gè)條件泻红，因此夭禽，算法的性能肯定不是最優(yōu)的。本題中谊路，由于鏈表具有有序性讹躯，因此，不需要對(duì)鏈表進(jìn)行兩次遍歷。所以蜀撑，有如下思路：用cur 指向鏈表第一個(gè)結(jié)點(diǎn)挤巡，此時(shí)需要分為以下兩種情況討論。
- 如果cur.data==cur.next.data酷麦，那么刪除cur.next結(jié)點(diǎn)矿卑。
- 如果cur.data!=cur.next.data，那么cur=cur.next沃饶，繼續(xù)遍歷其余結(jié)點(diǎn)母廷。
總結(jié)
對(duì)于無序單鏈表中，想要?jiǎng)h除其中重復(fù)的結(jié)點(diǎn)（多個(gè)重復(fù)結(jié)點(diǎn)保留一個(gè)）糊肤。刪除辦法有按照順序刪除琴昆、使用遞歸方式刪除以及可以使用空間換時(shí)間（HashSet中元素的唯一性）。
點(diǎn)贊越多馆揉，bug越少~
