82. 刪除排序鏈表中的重復(fù)元素 II
給定一個排序鏈表杆融，刪除所有含有重復(fù)數(shù)字的節(jié)點经备，只保留原始鏈表中 沒有重復(fù)出現(xiàn) 的數(shù)字知给。
示例 1:
輸入: 1->2->3->3->4->4->5
輸出: 1->2->5
示例 2:
輸入: 1->1->1->2->3
輸出: 2->3
方法1：遞歸
算法思路：
- 找終止條件：當
head指向鏈表只剩一個元素的時候号显，自然是不可重復(fù)的蛇数，因此return砚偶； - 以 1->1->1->2->3 為例：
- 則需要移動 next 直到出現(xiàn)與當前 head.value 不相等的情況（含null)
- 并且此時的 head 已經(jīng)不能要來批销，因為 head 已經(jīng)是重復(fù)的結(jié)點
- 以 1->2->3 為例：如果沒有出現(xiàn)上面的情況，則遞歸返回結(jié)點就作為 head 的子節(jié)點
參考代碼1：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
//如果是這種情況
// 1 --> 1 --> 1 --> 2 --> 3
// head next
//1.則需要移動next直到出現(xiàn)與當前head.value不相等的情況（含null）
//2.并且此時的head已經(jīng)不能要了染坯，因為已經(jīng)head是重復(fù)的節(jié)點
//--------------else-------------
// 1 --> 2 --> 3
// head next
//3.如果沒有出現(xiàn)1的情況均芽，則遞歸返回的節(jié)點就作為head的子節(jié)點
if (head.val == next.val) {
// 1
while (next != null && head.val == next.val){
next = next.next;
}
// 2
head = deleteDuplicates(next);
} else {
// 3
head.next = deleteDuplicates(next);
}
return head;
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：O(n)，n 是鏈表中結(jié)點數(shù)单鹿，因為鏈表中每個結(jié)點都檢查一次以確定是否重復(fù)掀宋。
- 空間復(fù)雜度：O(n)，遞歸過程使用的椫俪空間劲妙。
方法2：雙指針
算法思路：
使用雙指針的方式，定義 a , b 兩個指針儒喊。
考慮到一些邊界镣奋，比如 1->1->1->2->3 這種情況，需要把開頭的幾個 1 給去掉怀愧，我們增加一個 啞結(jié)點 唆途，方便邊界處理富雅。
初始的兩個指針如下：
- 將 a 指針指向啞結(jié)點
- 將 b 指針指向 head (啞結(jié)點的下一個結(jié)點)
如果 a 指向的值 不等于 b 指向的值，則兩個指針都前進一位肛搬，否則，就單獨移動 b毕贼，b 不斷往前走温赔，直到 a 指向的值 不等于 b 指向的值。
注意：這里不是直接比較 a.val == b.val , 這么比較不對鬼癣，因為初始的時候陶贼，a 指向的是啞結(jié)點，所以比較邏輯應(yīng)該是： a.next.val == b.next.val 待秃。
當兩個指針指向的值相等時拜秧，b 不斷往前移動，這里通過一個 while 循環(huán)判斷章郁，因為要過濾掉 1->2->2->2->3 重復(fù)的 2枉氮。
那么整個邏輯就是兩個 while , 但是時間復(fù)雜度 不是 ，而是
暖庄，空間上也只是常數(shù)級別聊替。
參考代碼2:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode a = dummy;
ListNode b = head;
while (b != null && b.next != null) {
// a 指向的值 與 b 指向的值不同，則兩個指針都往前走一步
if (a.next.val != b.next.val) {
a = a.next;
b = b.next;
} else {
// 如果a培廓、b指向的結(jié)點值相等惹悄，就不斷的移動b，直到a肩钠、b指向的值不等
while (b != null && b.next != null && a.next.val == b.next.val) {
b = b.next;
}
a.next = b.next;
b = b.next;
}
}
return dummy.next;
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：O(n)泣港。
- 空間復(fù)雜度：O(1)。
以上謝謝大家价匠，求贊求贊求贊当纱！
