Q:

Eliminate duplicates from Linked List using C++ program

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  193 
0

Given a sorted linked list (elements are sorted in ascending order). Eliminate duplicates from the given LL, such that output LL contains only unique elements.

Input format: Linked list elements (separated by space and terminated by 1)

    Sample Input 1 :
    1 2 3 3 3 4 4 5 5 5 7 -1

    Sample Output 1 :
    1 2 3 4 5 7

Description:

In this question, we are given a sorted linked list with duplicate elements in it. Our task is to remove the duplicate nodes of the linked list. Since the list is sorted, the duplicate elements will be present in consecutive orders, that makes the work a lot easier.

Example:

    Lets the list be:
    1->2->3->3->4->4->4->NULL
    The modified list will be:
    1->2->3->4->NULL

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

To solve this problem, we keep the temp pointer pointing to node. While(temp -> next != NULL), we check if the data of temp is equal to data of temp->next. If they are equal, we will point the temp-> next to temp -> next ->next.
Original LL: 3-> 3-> 4-> ...
After Change: 3-> 4-> ... Leaving out the middle 3->

This will keep on until we reached the end of the list and return head at the end.

Steps

    1.	1->2->3->3->4->4->4->NULL, temp = 1
    2.	1->2->3->3->4->4->4->NULL, temp = 2
    3.	1->2->3->3->4->4->4->NULL, temp = 3
    4.	1->2->3->4->4->4->NULL, temp = 4
    5.	1->2->3->4->4->NULL, temp = 4
    Finally,
    1->2->3->4->NULL

Function:

Node *removeDuplicate(Node* head){
	//temp pointing to head
	Node *temp = head;            
	while(temp->next != NULL && temp != NULL){
		//Duplicate Found
		if(temp->data == temp->next->data){      
			//DUplicate Removed
			temp -> next = temp ->next ->next;    
		}
		else{
			//No Duplicate Present
			temp = temp->next;               
		}
	}
	//Return Head
	return head;                
}

C++ Code:

#include<bits/stdc++.h>
using namespace std;

struct Node{// linked list Node
	int data;
	Node * next;
};

Node *newNode(int k){ //defining new node
	Node *temp = (Node*)malloc(sizeof(Node)); 
	temp->data = k; 
	temp->next = NULL; 
	return temp; 
}

//Used to add new node at the end of the list
Node *addNode(Node* head, int k){
	if(head == NULL){
		head = newNode(k);
	}
	else{
		Node * temp = head;
		Node * node = newNode(k);
		while(temp->next!= NULL){
			temp = temp->next;
		}
		temp-> next = node;
	}

	return head;
}

// Used to create new linked list and return head
Node *createNewLL(){
	int cont = 1;
	int data;
	Node* head = NULL;
	while(cont){
		cout<<"Enter the data of the Node"<<endl;
		cin>>data;
		head = addNode(head,data);
		cout<<"Do you want to continue?(0/1)"<<endl;
		cin>>cont;
	}
	return head;
}

//To print the Linked List
void *printLL(Node * head){
	while(head!= NULL){
		cout<<head->data<<"->";
		head = head-> next;
	}
	cout<<"NULL"<<endl;
}

//Function 
Node *removeDuplicate(Node* head){
	//temp pointing to head
	Node *temp = head;
	while(temp->next != NULL && temp != NULL){
		//Duplicate Found
		if(temp->data == temp->next->data){
			//DUplicate Removed
			temp -> next = temp ->next ->next;
		}
		else{
			//No Duplicate Present
			temp = temp->next;
		}
	}
	//Return Head
	return head;
}

//Driver Main
int main(){
	Node * head = createNewLL();
	cout<<"The linked list is"<<endl;
	printLL(head);

	head = removeDuplicate(head);
	cout<<"The new Linked List is" <<endl;
	printLL(head);

	return 0;
}

Output

 
Enter the data of the Node
1
Do you want to continue?(0/1)
1
Enter the data of the Node
1
Do you want to continue?(0/1)
1
Enter the data of the Node
2
Do you want to continue?(0/1)
1
Enter the data of the Node
2
Do you want to continue?(0/1)
1
Enter the data of the Node
3
Do you want to continue?(0/1)
1
Enter the data of the Node
4
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
1
Enter the data of the Node
5
Do you want to continue?(0/1)
0
The linked list is
1->1->2->2->3->4->5->5->5->NULL
The new Linked List is
1->2->3->4->5->NULL

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Find a Node in Linked List using C++ program... >>
<< Append Last N Nodes to First in the Linked List us...