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)