83. Remove Duplicates from Sorted List
Remove Duplicates from Sorted List (LeetCode 83) is a Easy 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
Remove Duplicates from Sorted List 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 input is a sorted linked list, think about how duplicates appear consecutively and how that can simplify your approach.
- Try traversing the list once and compare each node's value with the value of the next node to identify duplicates.
- When you find consecutive nodes with the same value, consider how you can modify the links to skip over duplicate nodes without creating new nodes.
The reference solution runs in O(n) time and O(1) space.
The Remove Duplicates from Sorted List solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: Linked List.
Reported in interviews at Amazon, Adobe, Goldman Sachs, Qualcomm.
How to practise Remove Duplicates from Sorted List 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 in the code editor, or read the Remove Duplicates from Sorted List editorial for a worked solution with its approach and complexity analysis.
Where Remove Duplicates from Sorted List 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
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 II — Medium, 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 FAQ
What is the LeetCode number of Remove Duplicates from Sorted List?
Remove Duplicates from Sorted List is LeetCode problem 83, rated Easy.
What pattern is used to solve Remove Duplicates from Sorted List?
Remove Duplicates from Sorted List 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?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Remove Duplicates from Sorted List?
Remove Duplicates from Sorted List has been reported in interviews at Amazon, Adobe, Goldman Sachs, Qualcomm.