Remove Duplicates from Sorted List solution and explanation
Google
TCS
9 more videos on this problem
Remove Duplicates from Sorted List - Leetcode 83 - PythonNeetCode · 10:47 · 79K views
LeetCode 83. Remove Duplicates from Sorted List Solution Explained - JavaNick White · 4:13 · 39K views
Remove Duplicates from Sorted List (LeetCode 83) | Full Solution with animations & Easy ExplanationNikhil Lohia · 13:50 · 23K views
Remove Duplicates from Sorted List - Leetcode 83 - Linked Lists (Python)Greg Hogg · 5:27 · 20K views
Leetcode | 83. Remove Duplicates from Sorted List | Easy | Java SolutionDeveloper Docs · 5:17 · 7K views
Remove Duplicates from Sorted List - LeetCode #83 - Python, JavaScript, Java, C++CodingNinja · 7:09 · 7K views
Remove Duplicates from Sorted List | LeetCode 83 | Coding Interview TutorialTerrible Whiteboard · 10:06 · 4K views
LeetCode 83: Remove Duplicates from Sorted List | C++Blake Wright · 7:18 · 3K views
Remove Duplicates from Sorted List - Leetcode 83 - JavaMastering Programming · 5:14 · 1K views
LeetCode 83 | Remove Duplicates from Sorted Linked List (Java + Whiteboard)Xavier Elon · 4:44 · 578 views
The problem
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.
Approach overview
Problem 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 1: Iterative Approach using Two Pointers
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* current = head;
while (current && current->next) {
if (current->val == current->next->val) {
ListNode* toDelete = current->next;
current->next = current->next->next;
delete toDelete;
} else {
current = current->next;
}
}
return head;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
function deleteDuplicates(head) {
let current = head;
while (current !== null && current.next !== null) {
if (current.val === current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode* current = head;
while (current != NULL && current->next != NULL) {
if (current->val == current->next->val) {
struct ListNode* toDelete = current->next;
current->next = current->next->next;
free(toDelete);
} else {
current = current->next;
}
}
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}The Python implementation defines a 'ListNode' class and a 'Solution' class containing 'deleteDuplicates'. This method iteratively traverses the list, compares current and next node values, and adjusts pointers to skip duplicates.
Time Complexity: O(n), where n is the number of elements in the linked list, as each node is visited once.
Space Complexity: O(1), no extra space is used other than pointers.
Approach 2: Recursive Approach
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
head.next = self.deleteDuplicates(head.next)
return head.next if head.val == head.next.val else headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return (head.val == head.next.val) ? head.next : head;
}
}struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
head->next = deleteDuplicates(head->next);
if (head->val == head->next->val) {
ListNode* toDelete = head->next;
head->next = head->next->next;
delete toDelete;
}
return head;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
function deleteDuplicates(head) {
if (!head || !head.next) return head;
head.next = deleteDuplicates(head.next);
return head.val === head.next.val ? head.next : head;
}#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (!head || !(head->next)) return head;
head->next = deleteDuplicates(head->next);
if (head->val == head->next->val) {
struct ListNode* temp = head->next;
head->next = head->next->next;
free(temp);
}
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = DeleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
}The Python solution leverages recursion to simplify duplicate removal in a sorted linked list. By comparing each node’s value with its successor, the list is adjusted to omit duplicates seamlessly.
Time Complexity: O(n), where n is the total number of nodes in the list.
Space Complexity: O(n), owing to the recursion stack consumption.
Approach 3: Single Pass
We use a pointer cur to traverse the linked list. If the element corresponding to the current cur is the same as the element corresponding to cur.next, we set the next pointer of cur to point to the next node of cur.next. Otherwise, it means that the element corresponding to cur in the linked list is not duplicated, so we can move the cur pointer to the next node.
After the traversal ends, return the head node of the linked list.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode::new(i32::MAX)));
let mut p = &mut dummy;
let mut current = head;
while let Some(mut node) = current {
current = node.next.take();
if p.as_mut().unwrap().val != node.val {
p.as_mut().unwrap().next = Some(node);
p = &mut p.as_mut().unwrap().next;
}
}
dummy.unwrap().next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach using Two Pointers | Time Complexity: O(n), where n is the number of elements in the linked list, as each node is visited once. |
| Recursive Approach | Time Complexity: O(n), where n is the total number of nodes in the list. |
| Single Pass | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Remove Duplicates from Sorted List easy or hard?
Remove Duplicates from Sorted List is classified as an Easy problem on LeetCode. The challenge focuses on basic linked list traversal and pointer manipulation rather than complex algorithms, making it a common introductory linked list interview question.
Remove Duplicates from Sorted List Python/Java solution
Both Python and Java implementations follow the same idea: iterate through the linked list and compare current.val with current.next.val. If they match, skip the duplicate node; otherwise move forward. The logic is identical across languages and runs in O(n) time with O(1) space.
How to solve Remove Duplicates from Sorted List in O(n)?
Traverse the sorted linked list with a pointer. If the current node and the next node have the same value, remove the duplicate by setting current.next = current.next.next. Otherwise move the pointer forward. Since each node is examined once, the algorithm runs in O(n) time.
What is the best approach for Remove Duplicates from Sorted List?
The iterative two-pointer approach is the best solution. Because the list is sorted, duplicates appear consecutively, so you only need to compare each node with its next node and skip duplicates. This processes the list in O(n) time while using O(1) extra space.
Is Remove Duplicates from Sorted List asked at Google/Amazon/Meta?
Linked list deduplication problems frequently appear in technical interviews at companies like Amazon, Google, and Meta. Variants include removing duplicates from unsorted lists, removing all duplicates, or handling arrays instead of linked lists.
What data structure is used in Remove Duplicates from Sorted List?
The problem is solved using a singly linked list and pointer manipulation. The optimal solution relies on comparing adjacent nodes and updating next pointers to remove duplicates without allocating additional data structures.
What is the time complexity of Remove Duplicates from Sorted List?
The optimal solution runs in O(n) time where n is the number of nodes in the linked list. Each node is visited once during traversal. The iterative approach uses O(1) space, while the recursive version uses O(n) stack space.