83. 刪除排序鏈表中的重復(fù)元素
給定一個排序鏈表，刪除所有重復(fù)的元素，使得每個元素只出現(xiàn)一次峭火。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
方法1：遍歷
算法思路：
這是一個簡單的問題毁习，僅測試你操作鏈表的結(jié)點(diǎn)指針的能力。由于輸入的鏈表已排序卖丸，因此我們可以通過將結(jié)點(diǎn)的值與它之后的結(jié)點(diǎn)的值進(jìn)行比較確定它是否為重復(fù)結(jié)點(diǎn)纺且。如果它重復(fù)，我們更改當(dāng)前結(jié)點(diǎn)的 next 指針稍浆，以便它跳過以下一個結(jié)點(diǎn)载碌，并指向下下個結(jié)點(diǎn)。
參考代碼1：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：O(n)衅枫，n 是鏈表中結(jié)點(diǎn)數(shù)嫁艇，因?yàn)殒湵碇忻總€結(jié)點(diǎn)都檢查一次以確定是否重復(fù)。
- 空間復(fù)雜度：O(1)弦撩，沒有使用額外的空間步咪。
方法1：遞歸
算法思路：
- 找終止條件：當(dāng)
head指向鏈表只剩一個元素的時候，自然是不可重復(fù)的益楼，因此return猾漫； - 想想應(yīng)該返回什么值：應(yīng)該返回的自然是已經(jīng)去重的鏈表的頭結(jié)點(diǎn)
- 遞歸每一步做什么：宏觀上考慮，此時
head.next已經(jīng)指向一個去重的鏈表感凤，而根據(jù)第二步悯周，我應(yīng)該返回一個去重的鏈表的頭節(jié)點(diǎn)。因此這一步應(yīng)該做的是判斷當(dāng)前的head和head.next是否相等陪竿，如果相等則說明重復(fù)來禽翼，返回head.next，否則返回head族跛。
參考代碼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;
}
head.next = deleteDuplicates(head.next);
if (head.val == head.next.val) {
head = head.next;
}
return head;
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：O(n)闰挡，n 是鏈表中結(jié)點(diǎn)數(shù)，因?yàn)殒湵碇忻總€結(jié)點(diǎn)都檢查一次以確定是否重復(fù)礁哄。
- 空間復(fù)雜度：O(n)解总，遞歸過程使用的棧空間姐仅。
以上謝謝大家，求贊求贊求贊刻盐！
