Remove Duplicates from Sorted List II solution and explanation
Google
9 more videos on this problem
Remove Duplicates from Sorted List II | Live Coding with Explanation | Leetcode - 82Algorithms Made Easy · 5:22 · 57K views
Remove Duplicates from Sorted List 2 (LeetCode 82) | Full Solution with animationsNikhil Lohia · 12:04 · 15K views
LeetCode 82. Remove Duplicates from Sorted List IIEngineering Digest · 6:40 · 8K views
[Java] Leetcode 82. Remove Duplicates from Sorted List II [Two Pointers #10]Eric Programming · 6:18 · 7K views
Leetcode - Remove Duplicates from Sorted List II (Python)Timothy H Chang · 8:00 · 6K views
Leetcode 82 Remove Duplicates from Sorted List II (Java)TheAnalyticGuy · 8:19 · 4K views
LeetCode 82 | Remove Duplicates from Sorted Linked List II | Solution Explained (Java)Xavier Elon · 4:08 · 2K views
Remove Duplicates from Sorted List II | Leetcode 82 | Live coding sessionCoding Decoded · 10:20 · 1K views
Remove Duplicates From Sorted Linked List | LeetCode 82 |Top Interview Question| Java DSA | GeeksterGeekster · 9:45 · 1K views
82. Remove Duplicates from Sorted List II | Leetcode | PythonAbdullah Arshed · 6:05 · 750 views
The problem
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.
Approach overview
Problem Overview: You are given a sorted linked list. If a value appears more than once, every node with that value must be removed. Only values that appear exactly once should remain in the final list.
Approach 1: Iterative Approach using Two Pointers (O(n) time, O(1) space)
The list is sorted, so duplicates always appear in consecutive nodes. Use two pointers to scan the list: a prev pointer tracking the last confirmed unique node and a curr pointer that scans forward. When curr encounters duplicates (multiple nodes with the same value), advance it until the value changes, then link prev.next to the first different node. A dummy head simplifies edge cases when duplicates appear at the beginning. This approach performs a single linear traversal and modifies pointers in-place, making it the most efficient solution.
This method relies on properties of a linked list and sequential traversal using a two pointers pattern. Because the list is sorted, you never need extra memory to track frequencies. Each node is visited once, giving O(n) time and O(1) auxiliary space.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution processes the list from the head and decides whether the current node should remain. If the next node has the same value, all nodes with that value must be skipped. Recursively move forward until a different value appears, then continue processing the remainder of the list. If the current value is unique, connect the node to the result of the recursive call on the next node.
This approach mirrors the problem definition closely and leads to concise code. However, recursion adds call stack overhead. In the worst case (a list with all unique values), recursion depth reaches n, giving O(n) extra space.
Recommended for interviews: The iterative two-pointer approach is what most interviewers expect. It demonstrates strong understanding of linked list pointer manipulation and efficient in-place processing. The recursive solution is elegant and useful for reasoning about the problem, but interviewers typically prefer the iterative O(1) space implementation.
Approach 1: Iterative Approach using Two Pointers
In this approach, we'll use two pointers: prev and current. The prev pointer will be the last node in the result list without duplicates, and current pointer will traverse the input list. We initialize a dummy node before the head to simplify the edge case management when duplicates are at the start of the list.
While traversing, if the current node has the same value as the next node, we keep moving forward to skip all nodes with this value. If prev.next points to the current node when a duplicate sequence starts, we simply remove the sequence by connecting prev to the node after the last duplicate.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev = dummy
while head:
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
prev.next = head.next
else:
prev = prev.next
head = head.next
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
prev.next = head.next;
} else {
prev = prev.next;
}
head = head.next;
}
return dummy.next;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while (head) {
if (head->next && head->val == head->next->val) {
while (head->next && head->val == head->next->val) {
head = head->next;
}
prev->next = head->next;
} else {
prev = prev->next;
}
head = head->next;
}
return dummy.next;
}function ListNode(val) {
this.val = val;
this.next = null;
}
function deleteDuplicates(head) {
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
while (head !== null) {
if (head.next !== null && head.val === head.next.val) {
while (head.next !== null && head.val === head.next.val) {
head = head.next;
}
prev.next = head.next;
} else {
prev = prev.next;
}
head = head.next;
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy;
struct ListNode* current = head;
while (current) {
// Check for duplicate sequences
while (current->next && current->val == current->next->val) {
current = current->next;
}
if (prev->next == current) {
prev = prev->next;
} else {
prev->next = current->next;
}
current = current->next;
}
return dummy.next;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
prev.next = head.next;
} else {
prev = prev.next;
}
head = head.next;
}
return dummy.next;
}
}The Python implementation follows the two-pointer approach using a dummy node. The head runs through the list, skipping duplicates and adjusting the prev link as needed. The final list is derived by retrieving dummy.next.
Time Complexity: O(n) because all nodes are considered iteratively.
Space Complexity: O(1) with minimal overhead.
Approach 2: Recursive Approach
This approach utilizes recursion to elegantly process the list for duplicates. The concept centers on calling a helper function that, at each level, processes the current node list by recursively evaluating burdens of duplicates. The recursion simplifies decision-making by naturally moving through the list and sorting out duplicate removal due to stack calls automatically handling execution follow-through.
Each call checks for duplicate patterns and recursively bridges connections between unique nodes. This allows the call stack to effectively tackle the transformation demands of duplicate filtering through returning modified structures created per 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:
return None
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
return self.deleteDuplicates(head.next)
else:
head.next = self.deleteDuplicates(head.next)
return headThe Python recursive solution systematically checks each node and its successively linked node's equality. When duplicates are found, the head progress skips them altogether, recursively pursuing a clean node linkage post-duplicate skipping.
Time Complexity: O(n), visiting each node once recursively.
Space Complexity: O(n), accounting for call stack space in recursion.
Approach 3: Single Pass
First, we create a dummy head node dummy, and set dummy.next = head. Then we create a pointer pre pointing to dummy, and a pointer cur pointing to head, and start traversing the linked list.
When the node value pointed by cur is the same as the node value pointed by cur.next, we let cur keep moving forward until the node value pointed by cur is different from the node value pointed by cur.next. At this point, we check whether pre.next is equal to cur. If they are equal, it means there are no duplicate nodes between pre and cur, so we move pre to the position of cur; otherwise, it means there are duplicate nodes between pre and cur, so we set pre.next to cur.next. Then we continue to move cur forward. Continue the above operation until cur is null, and the traversal ends.
Finally, return dummy.next.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function deleteDuplicates(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let pre = dummy;
let cur = head;
while (cur) {
while (cur.next && cur.val === cur.next.val) {
cur = cur.next;
}
if (pre.next === cur) {
pre = cur;
} else {
pre.next = cur.next;
}
cur = cur.next;
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre, cur := dummy, head
for cur != nil {
for cur.Next != nil && cur.Next.Val == cur.Val {
cur = cur.Next
}
if pre.Next == cur {
pre = cur
} else {
pre.Next = cur.Next
}
cur = cur.Next
}
return dummy.Next
}// 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(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode::new(101)));
let mut pev = dummy.as_mut().unwrap();
let mut cur = head;
let mut pre = 101;
while let Some(mut node) = cur {
cur = node.next.take();
if node.val == pre || (cur.is_some() && cur.as_ref().unwrap().val == node.val) {
pre = node.val;
} else {
pre = node.val;
pev.next = Some(node);
pev = pev.next.as_mut().unwrap();
}
}
dummy.unwrap().next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach using Two Pointers | Time Complexity: O(n) because all nodes are considered iteratively. |
| Recursive Approach | Time Complexity: O(n), visiting each node once recursively. |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Two Pointers | O(n) | O(1) | Best choice for interviews and production since it removes duplicates in-place with constant memory |
| Recursive Approach | O(n) | O(n) | Useful for conceptual clarity or when recursive list processing is preferred |
Frequently asked questions
Is Remove Duplicates from Sorted List II easy or hard?
The problem is classified as Medium difficulty. The challenge comes from correctly handling pointer updates and edge cases such as duplicates at the start or end of the list while maintaining a single-pass traversal.
How to solve Remove Duplicates from Sorted List II in O(n)?
Use a dummy head and two pointers. Traverse the list with a current pointer and detect runs of equal values. If duplicates are found, skip the entire block and connect the previous node directly to the next unique node. This single pass guarantees O(n) time complexity.
Remove Duplicates from Sorted List II Python or Java solution?
Both Python and Java implementations typically follow the same logic: create a dummy node, maintain previous and current pointers, detect duplicate sequences, and reconnect pointers to skip them. The algorithm runs in O(n) time with O(1) extra memory.
What is the best approach for Remove Duplicates from Sorted List II?
The iterative two-pointer approach is the best solution. Because the linked list is sorted, duplicates appear consecutively. By scanning once with a current pointer and maintaining a previous pointer to reconnect nodes, you can remove all duplicate groups in O(n) time and O(1) extra space.
What data structure is used in Remove Duplicates from Sorted List II?
The problem is based on a singly linked list. The solution relies on pointer manipulation and the two-pointer traversal technique to detect and remove duplicate sequences efficiently.
What is the time complexity of Remove Duplicates from Sorted List II?
The optimal solution runs in O(n) time where n is the number of nodes in the list. Each node is visited at most once during traversal. The iterative approach uses O(1) extra space, while the recursive approach requires O(n) stack space in the worst case.
Is Remove Duplicates from Sorted List II asked at Google, Amazon, or Meta?
This problem pattern frequently appears in interviews at large tech companies including Amazon, Google, and Meta. It tests linked list manipulation, pointer control, and handling edge cases such as duplicates at the head of the list.