Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Remove duplicates from a sorted Doubly Linked List

Easy
0/40
profile
Contributed by
245 upvotes
Asked in companies
AdobeAppleAmazon

Problem statement

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.


You are given a sorted doubly linked list of size 'n'.


Remove all the duplicate nodes present in the linked list.


Example :
Input: Linked List: 1 <-> 2 <-> 2 <-> 2 <-> 3

Output: Modified Linked List: 1 <-> 2 <-> 3

Explanation: We will delete the duplicate values ‘2’ present in the linked list.


Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains an integer 'n', the number of elements in the linked list.
The second line contains 'n' integers, the elements of the linked list separated by a single space.


Output Format :
Print a single line, the final linked list.


Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Sample Input 1 :
5
1 2 2 2 3


Sample Output 1 :
1 2 3


Explanation For Sample Input 1 :
We will delete the duplicate values ‘2’ present in the linked list.


Sample Input 2 :
4
1 2 3 4


Sample Output 2 :
1 2 3 4


Explanation For Sample Input 2 :
The list contains no duplicates, so the final list is unchanged.


Expected time complexity :
The expected time complexity is O('n').


Constraints :
1 <= 'n' <= 10^5
1 <= 'data' in any node <= 10^6

Time limit: 1 sec
Hint

If the next element is the same as the current one, try adjusting the links to remove the next element!

Approaches (1)
Brute Force

Check if the current element has the same value as the next element, if so adjust the pointers such that the next to next element of the current element is the next element. Refer to the steps below for a better understanding.

The steps are as follows :

  • Initialize ‘cur’ equal to ‘head’.
  • Run a while loop till ‘cur’ and ‘cur->next’ both are not NULL.
  • Check if the current element is equal to the next element, if so then set ‘cur->next’ equal to ‘cur->next->next’ so that the next to next element now becomes the next element (ultimately removing one of the duplicates). 
  • If the current element is different from the next element, then set the ‘cur’ pointer to point to the next element.
  • Finally, return ‘head’.
Time Complexity

O(n), where ‘n’ is the length of the linked list.

Each element in the input list is traversed exactly once, and the links are adjusted accordingly to remove duplicates.

Hence the time complexity is O(n).

Space Complexity

O(1)

No extra space is used except ‘cur’.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Remove duplicates from a sorted Doubly Linked List
All tags
Sort by
Search icon

Interview problems

TC = O(N) SC = O(1)

Node * removeDuplicates(Node *head){

    // Write your code here

    Node *temp = head;

    Node *temp2 = head->next;

    while(temp2 != nullptr){

        if(temp2->data == temp->data){

            while(temp2->data == temp->data){

                if(temp2->next == nullptr){

                    temp->next->prev = nullptr;

                    temp->next = nullptr;

                    break;

                } 

                temp2 = temp2->next;

                continue;

            }

            if(temp->next == nullptr) break;

            temp->next = temp2;

            temp2->prev = temp;

            temp = temp->next;

            temp2 = temp2->next;

        }

        else{

            temp = temp->next; 

            temp2 = temp2->next;

        }

    }

    return head;

}

10 views
0 replies
0 upvotes

Interview problems

best Optimized code C++

Node * removeDuplicates(Node *head)

{

    Node*temp=head;

    while(temp!=NULL && temp->next!=NULL){

        Node*nextnode=temp->next;

        while(nextnode!=NULL && nextnode->data == temp->data){

            nextnode=nextnode->next;

        }

        temp->next=nextnode;

        if(nextnode) nextnode->prev=temp;

        temp=temp->next;

    }

    return head;

}

11 views
1 reply
0 upvotes

Interview problems

C++ simple solution

Node * removeDuplicates(Node *head)

{

    // Write your code here

    if(head==NULL){

        return NULL;

    }

    Node* curr = head;

    while(curr!=NULL){

        if((curr->next!=NULL)&&curr->data == curr->next->data){

            Node* todelete = curr->next;

            delete(todelete);

            curr->next = curr->next->next;

            

            

            

        }

        else{

            curr = curr->next;

        }

    }

    return head;

}

programming

tutorial

21 views
0 replies
0 upvotes

Interview problems

All test cases passed, C++ solution

Node* removeDuplicates(Node *head)

{   

    if(head == NULL)

        return head;

    

    Node* current = head;

    Node* nextNode = current->next; 

    Node* duplicate = NULL;

 

    while(current != NULL && current->next != NULL){

 

        while(nextNode->data == current->data){

            duplicate = nextNode; 

            nextNode = nextNode->next; 

            delete duplicate;

 // always delete duplicate after updating nextNode 

 

            if(nextNode == NULL)

                break;     

        }

        current->next = nextNode;

        if(nextNode == NULL){

            break;

        }

        else{

            nextNode->prev = current;

            current = current->next;

            nextNode = nextNode->next;

        }

    }

    return head;

}

21 views
0 replies
0 upvotes

Interview problems

Java Easy Solution 🙌

public class Solution {

    public static Node uniqueSortedList(Node head) {

        // Write your code here.

        if(head==null || head.next==null) return head;

        Node p=head,n=head.next;

        while(n!=null){

            if(p.data!=n.data){

                p.next=n;

                p=p.next;

            }

            n=n.next;

        }

        if(p.next!=null) p.next=null;

        return head;

    }

}

35 views
0 replies
0 upvotes

Interview problems

Easy python solution

def removeDuplicates(head: Node) -> Node:

    curr = head

 

    while curr.next:

        if curr.data == curr.next.data:

            curr.next = curr.next.next

            continue

        

        curr = curr.next

    

    return head

9 views
0 replies
0 upvotes

Interview problems

Easy to underStand solution with line to line explanation.

Node * removeDuplicates(Node *head)

{

    // if the node don't have any element

   if(head == NULL){

       return  NULL;

   }

    // non empty list 

   Node* curr = head;

 

   while(curr != NULL){

 

      if( (curr -> next != NULL) && curr -> data == curr -> next -> data ){

          // if next is duplicates what to do 

          //1. remove the pointer and pointed it towards the next to next curr; 

          //2. delete the duplicate 

 

          Node* next_to_next = curr -> next -> next;  

          Node* deleteDuplicate = curr -> next; 

          delete(deleteDuplicate); // we deleted the next duplicate Node now, we pointer our curr to the next node

          curr -> next =  next_to_next ; 

   }else{ // if the next is not equal to current { != }

    curr = curr -> next; 

   }

   }

// return the head o

   return head; 

}

55 views
2 replies
0 upvotes

Interview problems

Java Solution

public class Solution {
    public static Node uniqueSortedList(Node head) {

        if(head == null || head.next == null){
            return head;
        }

        Node curr = head;

        while(curr != null){
            Node next = curr;
            while(next != null && next.data == curr.data){
                next = next.next;
            }
            curr.next = next;
            curr = curr.next;
        }

        return head;
    }
}
49 views
0 replies
1 upvote

Interview problems

easy cpp

Node* removeDuplicates(Node* head) {

    Node* temp = head;

    if (temp == NULL) {

        return head;

    }

    Node* nextNode = temp->next;

    while (temp != NULL && nextNode != NULL) {

        while (nextNode != NULL && temp->data == nextNode->data) {

            Node* remove = nextNode;

            nextNode = nextNode->next;

            delete remove;

            temp->next = nextNode;

            if (nextNode != NULL) {

                nextNode->prev = temp;

            }

        }

        temp = temp->next;

        if (temp != NULL) {

            nextNode = temp->next;

        }

    }

    return head;

}

 

88 views
0 replies
0 upvotes

Interview problems

c++ solution

Node * removeDuplicates(Node *head)

{

    if (head==nullptr || head->next == nullptr) return head ; 

    Node*temp = head ; 

    while(temp != nullptr && temp->next != nullptr)

    {

        if (temp->data == temp->next->data)

        {

           Node *a = temp->next ;

           Node*b = temp->prev ; 

           delete temp ;

           if (b != nullptr) {

             b->next = a;

             a->prev = b  ; 

           } else {

             head = a;

             a->prev = nullptr ;

           }

           temp = a ; 

        }

        else

        {

            temp=temp->next ; 

        }

 

    }

    return head ;

}

 

124 views
0 replies
0 upvotes
Full screen
Console