Last updated on January 29th, 2025 at 02:20 am
Here, we see a Remove Duplicates from Sorted List II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Linked List
Level of Question
Medium
Remove Duplicates from Sorted List II LeetCode Solution
Table of Contents
1. Problem Statement
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]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Two Pointers. Specifically, the code uses a slow pointer and a fast pointer to traverse the linked list and handle duplicates. The slow pointer is used to build the result list, while the fast pointer is used to detect duplicates by iterating through consecutive nodes with the same value.
3. Code Implementation in Different Languages
3.1 Remove Duplicates from Sorted List II C++
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
int flag = true; // should the current head be added ?
while(head){
while(head&&head->next&&head->val==head->next->val)
{
flag = false; // finds duplicate, set it to false
head = head->next;
}
if(flag) // if should be added
{
tail->next = head;
tail = tail->next;
}
head = head->next;
flag = true; // time for a new head value, set flag back to true
}
tail->next = nullptr; // Don't forget this... I did..
return dummy->next;
}
};
3.2 Remove Duplicates from Sorted List II Java
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0), fast = head, slow = dummy;
slow.next = fast;
while(fast != null) {
while (fast.next != null && fast.val == fast.next.val) {
fast = fast.next; //while loop to find the last node of the dups.
}
if (slow.next != fast) { //duplicates detected.
slow.next = fast.next; //remove the dups.
fast = slow.next; //reposition the fast pointer.
} else { //no dup, move down both pointer.
slow = slow.next;
fast = fast.next;
}
}
return dummy.next;
}
}
3.3 Remove Duplicates from Sorted List II JavaScript
var deleteDuplicates = function(head) {
if (head == null || head.next == null)
return head;
var fake = new ListNode(0);
fake.next = head;
var curr = fake;
while(curr.next != null && curr.next.next != null){ // curr.next means the next node of curr pointer and curr.next.next means the next of next of curr pointer...
if(curr.next.val == curr.next.next.val) {
let duplicate = curr.next.val;
while(curr.next !=null && curr.next.val == duplicate) {
curr.next = curr.next.next;
}
}
else{
curr = curr.next;
}
}
return fake.next;
};
3.4 Remove Duplicates from Sorted List II Python
class Solution(object):
def deleteDuplicates(self, head):
fake = ListNode(-1)
fake.next = head
curr, prev = head, fake
while curr:
while curr.next and curr.val == curr.next.val:
curr = curr.next
if prev.next == curr:
prev = prev.next
curr = curr.next
else:
prev.next = curr.next
curr = prev.next
return fake.next
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |
- The Two Pointers pattern is ideal for problems involving linked lists where traversal and modification are required simultaneously.
- The use of a dummy node simplifies edge cases, such as when the head itself is part of duplicates.
- The space complexity is O(1) because no additional data structures are used, and only a constant number of pointers are maintained.