Thank you. Implement the unsorted single linked list as we did in the class and
ID: 3709426 • Letter: T
Question
Thank you.Implement the unsorted single linked list as we did in the class and implement the following operations: d list, if there are multiple copies (-2 copies). 2. DeleteSecondLastDuplicat0: For any element in the linked list, if there are multiple copies (2 1. DeletelastDuplicat): For any element in the linke delete the last copy copies), delete the second last copy Test your program with the following operations: a) Insert 5 b) Insert 7 c) Insert 11 d) Insert 5 e) Insert 7 f) Insert 5 g) Print out the list h) Delete the last duplicate of 5 i) Print out the list j) Delete the last duplicate of 11 k) Print out the list 1) Insert 11 m) Insert 7 n) Print out the list o) Delete the second last duplicate of 5 p) Print out the list q) Delete the second last duplicate of 7 r) Print out the list
Explanation / Answer
// A linked list Node
struct Node {
int key;
struct Node* next;
};
void deleteLastDuplicate(Node* head, int key)
{
// Initialize previous of Node to be deleted
Node* x = NULL;
// Start from head and find the Node to be deleted
Node* temp = head;
while (temp) {
// If we found the key, update x
if (temp->key == key)
x = temp;
temp = temp->next;
}
// key occurs at-least once
if (x != NULL) {
// Copy key of next Node to x
x->key = x->next->key;
// Store and unlink next
temp = x->next;
x->next = x->next->next;
// Free memory for next
delete temp;
}
}
/* Utility function to create a new node with given key */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// This function prints contents of linked list
// starting from the given Node
void printList(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->key);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = newNode(5);
head->next = newNode(7);
head->next->next = newNode(11);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(7);
head->next->next->next->next->next = newNode(5);
printList(head);
deleteLastDuplicate(head, 5);
printList(head);
deleteLastDuplicate(head, 11);
printList(head);
head->next->next->next->next->next->next = newNode(11);
head->next->next->next->next->next->next->next = newNode(7);
printList(head);
deleteLastDuplicate(head, 5);
printList(head);
deleteLastDuplicate(head, 7);
printList(head);
return 0;
}
// A linked list Node
struct Node {
int key;
struct Node* next;
};
void deleteLastDuplicate(Node* head, int key)
{
// Initialize previous of Node to be deleted
Node* x = NULL;
// Start from head and find the Node to be deleted
Node* temp = head;
while (temp) {
// If we found the key, update x
if (temp->key == key)
x = temp;
temp = temp->next;
}
// key occurs at-least once
if (x != NULL) {
// Copy key of next Node to x
x->key = x->next->key;
// Store and unlink next
temp = x->next;
x->next = x->next->next;
// Free memory for next
delete temp;
}
}
/* Utility function to create a new node with given key */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// This function prints contents of linked list
// starting from the given Node
void printList(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->key);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = newNode(5);
head->next = newNode(7);
head->next->next = newNode(11);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(7);
head->next->next->next->next->next = newNode(5);
printList(head);
deleteLastDuplicate(head, 5);
printList(head);
deleteLastDuplicate(head, 11);
printList(head);
head->next->next->next->next->next->next = newNode(11);
head->next->next->next->next->next->next->next = newNode(7);
printList(head);
deleteLastDuplicate(head, 5);
printList(head);
deleteLastDuplicate(head, 7);
printList(head);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.