Description
給定一個已排序的鏈結串列的頭節點
head，刪除所有重複的元素，使每個元素只出現一次，回傳排序後的鏈結串列。
Example:
Input: head = [1,1,2,3,3] Output: [1,2,3]
Intuition#
核心思路：因為已排序，重複元素必定相鄰，只需比對當前節點與下一個節點的值。
- 已排序的鏈結串列中，重複元素一定是連續的
- 遍歷時若當前節點值等於下一個節點值，就跳過下一個節點
Approaches#
1: Recursive#
- 概念: 遞迴處理，若當前節點與下一個節點值相同則跳過當前節點
- 時間複雜度:
O(n) - 空間複雜度:
O(n)- 遞迴堆疊
class Solution {
fun deleteDuplicates(head: ListNode?): ListNode? {
if (head?.next == null) return head
head.next = deleteDuplicates(head.next)
return if (head.`val` == head.next?.`val`) head.next else head
}
}⭐2: Iterative#
- 概念: 遍歷鏈結串列，若 curr.val == curr.next.val 就跳過 next 節點
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun deleteDuplicates(head: ListNode?): ListNode? {
var curr = head
while (curr?.next != null) {
if (curr.`val` == curr.next!!.`val`) {
curr.next = curr.next!!.next
} else {
curr = curr.next
}
}
return head
}
}🔑 Takeaways#
- Pattern: 已排序資料的去重只需比對相鄰元素，這個概念在陣列和鏈結串列中都適用
- 關鍵技巧: 刪除重複時不移動 curr，因為新的 next 可能仍然是重複值