Last Updated on 2022-03-09 by Clay
題目
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3] Output: [2,3]
Constraints:
- The number of nodes in the list is in the range
[0, 300]. -100 <= Node.val <= 100- The list is guaranteed to be sorted in ascending order.
題目給定一組鏈結串列（linked-list）的資料，我們要把其中所有重複值的節點刪除（比方說 3 重複了兩次，就把所有 3 的節點全部刪掉）。
解題思路
當然，最簡單的方法還是把全部值用陣列儲存起來慢慢刪掉重複項…… 不過這樣空間複雜度應該比較糟糕一點。
想了很久，才發現這題可以用遞迴來解，我們只需要專注在處理跳過所有重複值的節點，所以每個當前值都要另外儲存起來。
複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
C++ 範例程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// Base case
if (head == nullptr || head->next == nullptr) {
return head;
}
// Init
int currVal = head->val;
ListNode* currNode = head->next;
// Recursion
if (currNode->val != currVal) {
head->next = deleteDuplicates(currNode);
return head;
}
else {
while (currNode != nullptr && currNode->val == currVal) {
currNode = currNode->next;
}
return deleteDuplicates(currNode);
}
}
};兩節點 Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case
if not head or not head.next:
return head
# Init
currVal = head.val
currNode = head.next
# Recursion
if currNode.val != currVal:
head.next = self.deleteDuplicates(currNode)
return head
else:
while currNode and currNode.val == currVal:
currNode = currNode.next
return self.deleteDuplicates(currNode)