題目描述
存在一個按升序排列的連結清單，給你這個連結清單的頭節點 head ，請你删除連結清單中所有存在數字重複情況的節點，隻保留原始連結清單中 沒有重複出現 的數字。
傳回同樣按升序排列的結果連結清單。
示例 1：
輸入：head = [1,2,3,3,4,4,5]
輸出：[1,2,5]
示例 2：
輸入：head = [1,1,1,2,3]
輸出：[2,3]
提示：
連結清單中節點數目在範圍 [0, 300] 内
-100 <= Node.val <= 100
題目資料保證連結清單已經按升序排列
解題思路一
掃描一次連結清單，統計數字在連結清單中出現的次數，再次周遊連結清單，當節點的值出現的次數大于等于2時，将該節點删除
import utils.ListNode;
import java.util.HashMap;
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode newHead=head;
HashMap<Integer,Integer> map=new HashMap();
while(head!=null){
int value=head.val;
if(map.get(value)==null){
map.put(value,1);
}else{
map.put(value,map.get(value)+1);
}
head=head.next;
}
ListNode sentinel=new ListNode(0);
sentinel.next=newHead;
ListNode pre=sentinel,cur=newHead;
while(cur!=null){
if(map.get(cur.val)>=2){
pre.next=cur.next;
cur=cur.next;
}else{
pre=pre.next;
cur=cur.next;
}
}
return sentinel.next;
}
public static void main(String[] args) {
ListNode head=new ListNode(1);
ListNode node2=new ListNode(1);
head.next=node2;
ListNode node3=new ListNode(2);
node2.next=node3;
node3.next=null;
Solution solution=new Solution();
solution.deleteDuplicates(head);
}
} 複制
複雜度分析
時間複雜度：O(n)，其中 n 是連結清單的長度。
空間複雜度：O(n)，其中 n 是連結清單的長度。
解題思路二
由于給定的連結清單是排好序的，是以重複的元素在連結清單中出現的位置是連續的，是以我們隻需要對連結清單進行一次周遊，就可以删除重複的元素。由于連結清單的頭節點可能會被删除，是以我們需要額外使用一個哨兵節點（sentinel node）指向連結清單的頭節點。
具體地，我們從指針 cur 指向連結清單的啞節點，随後開始對連結清單進行周遊。如果目前 cur.next 與 cur.next.next 對應的元素相同，那麼我們就需要将 cur.next 以及所有後面擁有相同元素值的連結清單節點全部删除。我們記下這個元素值 x，随後不斷将 cur.next 從連結清單中移除，直到 cur.next 為空節點或者其元素值不等于 x 為止。此時，我們将連結清單中所有元素值為 x 的節點全部删除。
如果目前cur.next 與cur.next.next 對應的元素不相同，那麼說明連結清單中隻有一個元素值為 cur.next 的節點，那麼我們就可以将cur 指向 cur.next。
當周遊完整個連結清單之後，我們傳回連結清單的的哨兵節點的下一個節點 sentinel.next 即可。
細節
需要注意cur.next 以及 cur.next.next 可能為空節點，如果不加以判斷，可能會産生運作錯誤。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode sentinel=new ListNode(0,head);
ListNode cur=sentinel;
while(cur.next!=null&&cur.next.next!=null){
if(cur.next.val==cur.next.next.val){
int x=cur.next.val;
while(cur.next!=null&&cur.next.val==x){
cur.next=cur.next.next;
}
}else{
cur=cur.next;
}
}
return sentinel.next;
}
public static void main(String[] args) {
ListNode head=new ListNode(1);
ListNode node2=new ListNode(1);
head.next=node2;
ListNode node3=new ListNode(2);
node2.next=node3;
node3.next=null;
Solution solution=new Solution();
solution.deleteDuplicates(head);
}
} 複制
複雜度分析
時間複雜度：O(n)，其中 n 是連結清單的長度。
空間複雜度：O(1)。