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:
[0, 300].-100 <= Node.val <= 100Problem Overview: Given the head of a sorted linked list, remove duplicate nodes so each value appears only once. The list must remain sorted and you should return the modified head of the list.
The key detail is that the list is already sorted. That means duplicates always appear next to each other. Instead of storing values in a set or reordering nodes, you simply compare each node with its next neighbor and skip duplicates.
Approach 1: Iterative Two Pointers (O(n) time, O(1) space)
This approach walks through the linked list once using a pointer called current. Because the list is sorted, duplicate values will always appear consecutively. When current.val == current.next.val, you remove the duplicate by updating the pointer: current.next = current.next.next. Otherwise, move the pointer forward normally.
The algorithm performs a single pass through the list, comparing each node with the next node. No extra data structures are required, which keeps space usage constant. This pattern is closely related to the two pointers technique, where one pointer scans the list while conditionally adjusting the next reference. Time complexity is O(n) since every node is visited once, and space complexity is O(1) because the list is modified in place.
This is the most common and practical solution. It’s straightforward, efficient, and works well for long lists without risking stack overflow.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution processes the list from the front and lets recursion handle the rest of the nodes. If the current node has the same value as its next node, skip the duplicate by returning the recursive result of head.next. Otherwise, connect the current node to the processed remainder of the list using head.next = deleteDuplicates(head.next).
This approach naturally fits problems where the structure repeats itself at every node. Each recursive call processes one node and reduces the problem size by one element. The algorithm still visits each node once, giving O(n) time complexity. However, recursion adds call stack overhead, resulting in O(n) auxiliary space.
Recursion is clean and expressive, especially if you're comfortable with recursion patterns on linked lists. However, most production code prefers the iterative version because it avoids stack usage.
Recommended for interviews: The iterative two-pointer approach is the expected solution. It demonstrates that you recognize the sorted property and can modify a linked list in place with O(1) extra space. Mentioning recursion as an alternative shows deeper understanding, but the iterative method is usually what interviewers want to see first.
This approach uses two pointers to traverse the linked list. It compares the current node with the next node. If they have the same value, update the next pointer of the current node to skip the duplicate. Otherwise, move to the next node. This ensures that each element appears only once while maintaining the sorted order.
This C code defines a function to delete duplicates from a sorted linked list. It uses a single while loop to traverse the list, comparing the value of the current node with the next node. If they match, the next pointer is adjusted to skip the duplicate, effectively deleting it. Memory for the deleted node is freed to avoid leaks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the list, since we traverse each node once.
Space Complexity: O(1), as no additional space is used apart from a few pointers.
This approach employs recursion to solve the problem. The base case checks if the current node is null or has no next node. For other cases, if the current node and the next node have the same value, the next pointer is adjusted to the result of the recursion call. Otherwise, move to the next node using recursion.
This C function utilizes recursion to remove duplicate nodes. It recursively processes nodes, checking if current and next nodes have the same value, and adjusts the pointers accordingly, freeing memory for duplicate nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes, each node is visited once.
Space Complexity: O(n), due to recursion stack space.
| Approach | Complexity |
|---|---|
| Iterative Approach using Two Pointers | Time Complexity: O(n), where n is the number of nodes in the list, since we traverse each node once. |
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes, each node is visited once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Two Pointers | O(n) | O(1) | Best choice for interviews and production when the list is sorted and duplicates are adjacent |
| Recursive Approach | O(n) | O(n) | Useful for practicing recursion on linked lists or when writing concise recursive logic |
Remove Duplicates from Sorted Array - Leetcode 26 - Python • NeetCode • 246,487 views views
Watch 9 more video solutions →Practice Remove Duplicates from Sorted List with our built-in code editor and test cases.
Practice on FleetCode