Remove Duplicate Nodes Linked List — Problem Statement & Solution Guide
Linked ListEasyTwo Pointers
TimeO(N)
|SpaceO(1)
Problem Description
Given the head of a sorted singly linked list, delete all duplicate nodes such that each element appears only once.
Examples
Example 1
Input
1 -> 1 -> 2 -> 3 -> 3 -> 3
Output
1 -> 2 -> 3
Explanation: Step-by-step: with input 1 -> 1 -> 2 -> 3 -> 3 -> 3, we remove the duplicate nodes (1 and 3), giving output 1 -> 2 -> 3
Example 2
Input
1 -> 2 -> 3 -> 4 -> 5
Output
1 -> 2 -> 3 -> 4 -> 5
Explanation: Step-by-step: with input 1 -> 2 -> 3 -> 4 -> 5, there are no duplicate nodes, so the output remains the same
Constraints
- The number of nodes in the list is in the range [0, 3000].
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.
Optimal Approach & Strategy
Traverse the sorted list with a single pointer. If curr.val == curr.next.val, skip curr.next in O(N) time and O(1) space.
Brute Force Approach
Collect all values in a set and rebuild the linked list.
Verified Code Solutions
JavaScript Solution
Time: O(N)
function deleteDuplicates(head) {
let current = head;
while (current && current.next) {
if (current.val === current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* current = head;
while (current && current->next) {
if (current->val == current->next->val) {
current->next = current->next->next;
} else {
current = current->next;
}
}
return head;
}
}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;
}
}class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(self, head):
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return headfunction deleteDuplicates(head) {
let current = head;
while (current && current.next) {
if (current.val === current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}Asked in Top Tech Interviews
AdobeAmazonUber
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.