MediumNo. 1836LeetCode Premium
Remove Duplicates From an Unsorted Linked List — LeetCode 1836 Python Solution
- Pattern
- Linked List
- Topics
- Hash Table, 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
# 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.nextComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the length of the linked list
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0138 | Copy List with Random Pointer | Medium |
| 0141 | Linked List Cycle | Easy |
| 0142 | Linked List Cycle II | Medium |
| 0146 | LRU Cache | Medium |
| 0160 | Intersection of Two Linked Lists | Easy |
| 0355 | Design Twitter | Medium |
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.