Given a sorted doubly linked list containing n nodes. The problem is to remove duplicate nodes from the given list.
Examples:
Algorithm:
removeDuplicates(head_ref, x) if head_ref == NULL return Initialize current = head_ref while current->next != NULL if current->data == current->next->data deleteNode(head_ref, current->next) else current = current->next
The algorithm for deleteNode(head_ref, current) (which deletes the node using the pointer to the node) is discussed in this post.
C++
/* C++ implementation to remove duplicates from a sorted doubly linked list */ #include <bits/stdc++.h> using namespace std; /* a node of the doubly linked list */ struct Node { int data; struct Node* next; struct Node* prev; }; /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ void deleteNode( struct Node** head_ref, struct Node* del) { /* base case */ if (*head_ref == NULL || del == NULL) return ; /* If node to be deleted is head node */ if (*head_ref == del) *head_ref = del->next; /* Change next only if node to be deleted is NOT the last node */ if (del->next != NULL) del->next->prev = del->prev; /* Change prev only if node to be deleted is NOT the first node */ if (del->prev != NULL) del->prev->next = del->next; /* Finally, free the memory occupied by del*/ free (del); } /* function to remove duplicates from a sorted doubly linked list */ void removeDuplicates( struct Node** head_ref) { /* if list is empty */ if ((*head_ref) == NULL) return ; struct Node* current = *head_ref; struct Node* next; /* traverse the list till the last node */ while (current->next != NULL) { /* Compare current node with next node */ if (current->data == current->next->data) /* delete the node pointed to by 'current->next' */ deleteNode(head_ref, current->next); /* else simply move to the next node */ else current = current->next; } } /* Function to insert a node at the beginning of the Doubly Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* since we are adding at the begining, prev is always NULL */ new_node->prev = NULL; /* link the old list off the new node */ new_node->next = (*head_ref); /* change prev of head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given doubly linked list */ void printList( struct Node* head) { /* if list is empty */ if (head == NULL) cout << "Doubly Linked list empty" ; while (head != NULL) { cout << head->data << " " ; head = head->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Create the doubly linked list: 4<->4<->4<->4<->6<->8<->8<->10<->12<->12 */ push(&head, 12); push(&head, 12); push(&head, 10); push(&head, 8); push(&head, 8); push(&head, 6); push(&head, 4); push(&head, 4); push(&head, 4); push(&head, 4); cout << "Original Doubly linked list:n" ; printList(head); /* remove duplicate nodes */ removeDuplicates(&head); cout << "
Doubly linked list after" " removing duplicates:n" ; printList(head); return 0; } |
Java
/* Java implementation to remove duplicates from a sorted doubly linked list */ public class removeDuplicatesFromSortedList { /* function to remove duplicates from a sorted doubly linked list */ public static void removeDuplicates(Node head) { /* if list is empty */ if (head== null ) return ; Node current = head; while (current.next != null ) { /* Compare current node with next node */ if (current.data == current.next.data) /* delete the node pointed to by ' current->next' */ deleteNode(head, current.next); /* else simply move to the next node */ else current = current.next; } /* traverse the list till the last node */ while (current.next != null ) { /* Compare current node with next node */ if (current.data == current.next.data) /* delete the node pointed to by 'current->next' */ deleteNode(head, current.next); /* else simply move to the next node */ else current = current.next; } } /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ public static void deleteNode(Node head, Node del) { /* base case */ if (head== null || del== null ) { return ; } /* If node to be deleted is head node */ if (head==del) { head=del.next; } /* Change next only if node to be deleted is NOT the last node */ if (del.next!= null ) { del.next.prev=del.prev; } /* Change prev only if node to be deleted is NOT the first node */ if (del.prev != null ) del.prev.next = del.next; } /* Function to insert a node at the beginning of the Doubly Linked List */ public static Node push(Node head, int data) { /* allocate node */ Node newNode= new Node(data); /* since we are adding at the begining, prev is always NULL */ newNode.prev= null ; /* link the old list off the new node */ newNode.next =head; /* change prev of head node to new node */ if (head!= null ) { head.prev=newNode; } head=newNode; return head; } /* Function to print nodes in a given doubly linked list */ public static void printList(Node head) { if (head == null ) System.out.println( "Doubly Linked list empty" ); while (head != null ) { System.out.print(head.data+ " " ) ; head = head.next; } } public static void main(String args[]) { Node head= null ; head=push(head, 12 ); head=push(head, 12 ); head=push(head, 10 ); head=push(head, 8 ); head=push(head, 8 ); head=push(head, 6 ); head=push(head, 4 ); head=push(head, 4 ); head=push(head, 4 ); head=push(head, 4 ); System.out.println( "Original Doubly LinkedList" ); printList(head); /* remove duplicate nodes */ removeDuplicates(head); System.out.println( "
Doubly linked list after removing duplicates:" ); printList(head); } } class Node { int data; Node next,prev; Node( int data) { this .data=data; next= null ; prev= null ; } } //This code is contributed by Gaurav Tiwari |
C#
/* C# implementation to remove duplicates from a sorted doubly linked list */ using System; public class removeDuplicatesFromSortedList { /* function to remove duplicates from a sorted doubly linked list */ public static void removeDuplicates(Node head) { /* if list is empty */ if (head == null ) return ; Node current = head; while (current.next != null ) { /* Compare current node with next node */ if (current.data == current.next.data) /* delete the node pointed to by ' current->next' */ deleteNode(head, current.next); /* else simply move to the next node */ else current = current.next; } /* traverse the list till the last node */ while (current.next != null ) { /* Compare current node with next node */ if (current.data == current.next.data) /* delete the node pointed to by 'current->next' */ deleteNode(head, current.next); /* else simply move to the next node */ else current = current.next; } } /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ public static void deleteNode(Node head, Node del) { /* base case */ if (head == null || del == null ) { return ; } /* If node to be deleted is head node */ if (head == del) { head = del.next; } /* Change next only if node to be deleted is NOT the last node */ if (del.next != null ) { del.next.prev = del.prev; } /* Change prev only if node to be deleted is NOT the first node */ if (del.prev != null ) del.prev.next = del.next; } /* Function to insert a node at the beginning of the Doubly Linked List */ public static Node push(Node head, int data) { /* allocate node */ Node newNode = new Node(data); /* since we are adding at the begining, prev is always NULL */ newNode.prev = null ; /* link the old list off the new node */ newNode.next = head; /* change prev of head node to new node */ if (head != null ) { head.prev = newNode; } head = newNode; return head; } /* Function to print nodes in a given doubly linked list */ public static void printList(Node head) { if (head == null ) Console.WriteLine( "Doubly Linked list empty" ); while (head != null ) { Console.Write(head.data + " " ) ; head = head.next; } } // Driver code public static void Main(String []args) { Node head = null ; head = push(head, 12); head = push(head, 12); head = push(head, 10); head = push(head, 8); head = push(head, 8); head = push(head, 6); head = push(head, 4); head = push(head, 4); head = push(head, 4); head = push(head, 4); Console.WriteLine( "Original Doubly LinkedList" ); printList(head); /* remove duplicate nodes */ removeDuplicates(head); Console.WriteLine( "
Doubly linked list after" + "removing duplicates:" ); printList(head); } } public class Node { public int data; public Node next,prev; public Node( int data) { this .data = data; next = null ; prev = null ; } } // This code is contributed by 29AjayKumar. |
Output:
Original Doubly linked list: 4 4 4 4 6 8 8 10 12 12 Doubly linked list after removing duplicates: 4 6 8 10 12
Time Complexity: O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments