Remove Duplicates from Sorted List LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance eBay Facebook Goldman Sachs Google Microsoft Oracle PayPal Qualcomm YahooViews 4174

Problem Statement

Remove Duplicates from Sorted List LeetCode Solution – We are given the head of a sorted linked list. We are asked to delete all the duplicates such that each element appears only once and return the linked list sorted as well.

Examples & Explanations

Example 1:

Remove Duplicates from Sorted List LeetCode Solution

Input: head = [1,1,2]
Output: [1,2]
Explanation: node 1 appears twice, hence it is removed

Example 2:

Remove Duplicates from Sorted List LeetCode Solution

Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: node 1 & 3 both are appearing twice and hence they are removed

Approach

The idea is simple, we will keep 2 pointers- a slow pointer, prev & a fast pointer, curr. If the value of curr is equal to the value of prev, it means the value is present in the linked list, hence we do not need to include curr again in the linked list, so we increment the value of curr else we increment both the pointers.

Note (Edge case): Once the curr hits NULL, we set the next of prev to NULL.

Code

C++ code for Remove Duplicates from Sorted List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL || head->next==NULL) return head;
        
        ListNode* prev = head;
        ListNode* curr=head->next;
        
        while(curr!=NULL) {
            if(prev->val == curr->val) {
                curr=curr->next;
            }
            else {
                prev->next=curr;
                prev=curr;
                curr=prev->next;
            }
        }
        prev->next=NULL;
        return head;
    }
};

Java code for Remove Duplicates from Sorted List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {        
        if(head==null || head.next==null) return head;
        
        ListNode prev = head;
        ListNode curr=head.next;
        
        while(curr!=null) {
            if(prev.val == curr.val) {
                curr=curr.next;
            }
            else {
                prev.next=curr;
                prev=curr;
                curr=prev.next;
            }
        }
        prev.next=null;
        return head;
    }
}

Complexity Analysis for Remove Duplicates from Sorted List LeetCode Solution

  • Time complexity: O(n)
    • Because each node in the list is checked exactly once to determine if it is a duplicate or not, the total run time is O(n), where n is the number of nodes in the list.
  • Space complexity: O(1)
    • No additional space is used.
Translate »