一、題目描述

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

二、題目解析

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

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

具體操作如下：

1、設(shè)置一個指針cur，指向鏈表的頭節(jié)點，從鏈表的頭節(jié)點開始訪問每一個節(jié)點。

2、開始不斷遍歷鏈表。

3、在訪問過程中，只要當(dāng)前節(jié)點和當(dāng)前節(jié)點的下一個節(jié)點有值，就不斷訪問下去

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

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

6、當(dāng)前節(jié)點和當(dāng)前節(jié)點的下一個節(jié)點不相同，那么 cur 這個節(jié)點可以保留下來，繼續(xù)訪問后面的節(jié)點

三、參考代碼

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

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

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

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

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

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

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

審核編輯：劉清