What is the time complexity of LeetCode 1836. Remove Duplicates From an Unsorted Linked List?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1836. Remove Duplicates From an Unsorted Linked List?

The Python solution on this page uses O(n), where n is the length of the linked list auxiliary space.

Remove Duplicates From an Unsorted Linked List — LeetCode 1836 Python Solution

MediumLeetCode PremiumHash TableLinked List

Problem: #1836
Pattern: Linked List
Reading time: 4 min
Source: leetcode.com

The problem

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions.

Example

Input: head = [1,2,3,2]
Output: [1,3]
Explanation: 2 appears twice in the linked list, so all 2's should be deleted. After deleting all 2's, we are left with [1,3].

Python solution

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        cnt = Counter()
        cur = head
        while cur:
            cnt[cur.val] += 1
            cur = cur.next
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur:
            if cnt[cur.val] > 1:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
        return dummy.next

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the linked list auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1836. Remove Duplicates From an Unsorted Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1836. Remove Duplicates From an Unsorted Linked List?: LeetCode 1836. Remove Duplicates From an Unsorted Linked List is rated Medium on LeetCode.
What is the time complexity of LeetCode 1836. Remove Duplicates From an Unsorted Linked List?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1836. Remove Duplicates From an Unsorted Linked List?: The Python solution on this page uses O(n), where n is the length of the linked list auxiliary space.
What topics does LeetCode 1836. Remove Duplicates From an Unsorted Linked List cover?: LeetCode 1836. Remove Duplicates From an Unsorted Linked List is tagged Hash Table and Linked List on LeetCode.
Is LeetCode 1836. Remove Duplicates From an Unsorted Linked List a premium problem?: Yes. LeetCode 1836. Remove Duplicates From an Unsorted Linked List is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.