一、題目描述

給定一個(gè)已排序的鏈表的頭head，刪除所有重復(fù)的元素，使每個(gè)元素只出現(xiàn)一次。返回已排序的鏈表。

二、題目解析

由于給定的鏈表是排好序的，因此重復(fù)的元素在鏈表中出現(xiàn)的位置是連續(xù)的，這個(gè)很關(guān)鍵。

因此我們只需要對(duì)鏈表進(jìn)行一次遍歷，就可以刪除重復(fù)的元素。

具體操作如下：

1、設(shè)置一個(gè)指針cur，指向鏈表的頭節(jié)點(diǎn)，從鏈表的頭節(jié)點(diǎn)開(kāi)始訪(fǎng)問(wèn)每一個(gè)節(jié)點(diǎn)。

2、開(kāi)始不斷遍歷鏈表。

3、在訪(fǎng)問(wèn)過(guò)程中，只要當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)有值，就不斷訪(fǎng)問(wèn)下去

4、當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)有兩種關(guān)系。

5、當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)相同，此時(shí)要?jiǎng)h除重復(fù)元素， 由于鏈表已經(jīng)是排序的，所以去重操作只需要跳過(guò)后面這個(gè)重復(fù)的節(jié)點(diǎn)就行。

6、當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不相同，那么 cur 這個(gè)節(jié)點(diǎn)可以保留下來(lái)，繼續(xù)訪(fǎng)問(wèn)后面的節(jié)點(diǎn)

三、參考代碼

// LeetCode 100題精講：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
//作者：程序員吳師兄
//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
classSolution{
publicListNodedeleteDuplicates(ListNodehead){
//從鏈表的頭節(jié)點(diǎn)開(kāi)始訪(fǎng)問(wèn)每一個(gè)節(jié)點(diǎn)
ListNodecur=head;

//在訪(fǎng)問(wèn)過(guò)程中，只要當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)有值，就不斷訪(fǎng)問(wèn)下去
while(cur!=null&&cur.next!=null){

//當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)有兩種關(guān)系

//1、當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)相同，此時(shí)要?jiǎng)h除重復(fù)元素
//由于鏈表已經(jīng)是排序的，所以去重操作只需要跳過(guò)后面這個(gè)重復(fù)的節(jié)點(diǎn)就行
if(cur.val==cur.next.val){

//執(zhí)行這個(gè)操作之后，cur.next被跳過(guò)去了
cur.next=cur.next.next;

//2、當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不相同，那么cur這個(gè)節(jié)點(diǎn)可以保留下來(lái)，繼續(xù)訪(fǎng)問(wèn)后面的節(jié)點(diǎn)
}else{
//繼續(xù)訪(fǎng)問(wèn)后面的節(jié)點(diǎn)
cur=cur.next;
}
}

//返回鏈表的頭節(jié)點(diǎn)就是結(jié)果
returnhead;
}
}

審核編輯：劉清