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