82. Remove Duplicates from Sorted List II
Remove Duplicates from Sorted List II (LeetCode 82) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
How to solve Remove Duplicates from Sorted List II
Remove Duplicates from Sorted List II is a In-Place Linked List Reversal problem, part of Linked List Manipulation Patterns. Master in-place linked list reversal including full reversal, partial reversal, and k-group reversal techniques.
Work towards the solution in these steps:
- Since the list is sorted, duplicates will be grouped together; consider how you can traverse the list to identify these groups effectively.
- Using a dummy node before the head can simplify edge cases where the first few nodes are duplicates; think about how this helps in removing nodes safely.
- While traversing, use pointers to detect when consecutive nodes have the same value, and skip all nodes with that value entirely.
The reference solution runs in O(n) time and O(1) space.
The Remove Duplicates from Sorted List II solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: Linked List, Two Pointers.
Reported in interviews at Amazon, Bloomberg.
How to practise Remove Duplicates from Sorted List II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Remove Duplicates from Sorted List II in the code editor, or read the Remove Duplicates from Sorted List II editorial for a worked solution with its approach and complexity analysis.
Where Remove Duplicates from Sorted List II sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- In-place Reversal subpattern
- The full DSA patterns sheet
Problems related to Remove Duplicates from Sorted List II
Other problems that use the same In-place Reversal and Linked List Manipulation Patterns techniques:
- Palindrome Linked List — Easy, same subpattern
- Remove Duplicates from Sorted List — Easy, same subpattern
- Reverse Linked List — Easy, same subpattern
- Reverse Linked List II — Medium, same subpattern
- Reverse Nodes in k-Group — Hard, same subpattern
- Add Two Numbers — Medium, same pattern
Remove Duplicates from Sorted List II FAQ
What is the LeetCode number of Remove Duplicates from Sorted List II?
Remove Duplicates from Sorted List II is LeetCode problem 82, rated Medium.
What pattern is used to solve Remove Duplicates from Sorted List II?
Remove Duplicates from Sorted List II is a In-Place Linked List Reversal problem. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
What is the time complexity of Remove Duplicates from Sorted List II?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Remove Duplicates from Sorted List II?
Remove Duplicates from Sorted List II has been reported in interviews at Amazon, Bloomberg.