Watch 10 video solutions for Remove Duplicates from Sorted List, a easy level problem involving Linked List. This walkthrough by NeetCode has 77,580 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: You get the head of a sorted singly linked list. Because the list is sorted, duplicate values appear next to each other. Remove the extra occurrences so each value appears only once and return the updated list.
Approach 1: Iterative Two Pointers (O(n) time, O(1) space)
The sorted order gives the key insight: duplicates always appear consecutively. Traverse the linked list with a pointer called current. Compare current.val with current.next.val. If both values match, skip the duplicate node by updating current.next = current.next.next. If they differ, move the pointer forward. Every node is processed once, and duplicate nodes are removed in-place without creating new nodes.
This approach relies on pointer manipulation rather than extra memory. Because the structure is already sorted, there is no need for hash sets or additional data structures. The traversal performs constant work per node, giving O(n) time complexity and O(1) space complexity. This is the most practical solution and the one expected in interviews when working with sorted linked lists.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution processes the list from the head while letting recursion handle the rest of the nodes. Call the function on head.next to deduplicate the remainder of the list. After recursion returns, compare head.val with head.next.val. If they are equal, skip the next node by returning head.next; otherwise keep the current node and return head.
This approach mirrors the natural recursive structure of a list: each node decides whether to keep or discard its neighbor after the remainder is cleaned. The algorithm still visits every node exactly once, so the runtime remains O(n). However, recursion introduces call stack usage proportional to the list length, leading to O(n) auxiliary space. It’s a clean conceptual solution and often appears when practicing recursion with linked structures.
Recommended for interviews: The iterative two-pointer solution is the expected answer. Interviewers want to see that you recognize the sorted property and remove duplicates with direct pointer updates. Mentioning the recursive variant demonstrates deeper understanding of list processing, but the iterative approach is more memory-efficient and production-friendly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Two Pointers | O(n) | O(1) | Best choice when the linked list is already sorted and you want an in-place, memory‑efficient solution |
| Recursive Approach | O(n) | O(n) | Useful for practicing recursion with linked lists or when expressing the logic recursively is clearer |