Description
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example 1:
Input: head = [1,1,2] Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3] Output: [1,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.
Explanation
Have a dictionary to track the visited node values.
Python Solution
# 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: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
visited = set()
while head and head.next:
visited.add(head.val)
while head.next and head.next.val in visited:
head.next = head.next.next
head = head.next
return dummy.next- Time Complexity: O(N).
- Space Complexity: O(N).