inactive

Prackya wants to implement a function to delete the middle node of a singly linked list. She wants you to write a program that takes user input to construct a linked list, inserts nodes at the end, and then deletes the middle node if it exists. If the linked list has an even number of nodes, the function should delete the second middle node. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5. For example, if the given linked list is 1->2->3->4->5->6, then it should be modified to 1->2->3->5->6.

#include <iostream> struct Node { int data; Node* next; Node(int data) : data(data), next(nullptr) {} }; void swapPairs(Node* head) { Node* current = head; while (current != nullptr && current->next != nullptr) { // Swap the data of adjacent nodes int temp = current->data; current->data = current->next->data; current->next->data = temp; // Move current to the next even node current = current->next->next; } } void printLinkedList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } int main() { int n; std::cin >> n; Node* head = nullptr; Node* tail = nullptr; for (int i = 0; i < n; ++i) { int value; std::cin >> value; Node* newNode = new Node(value); if (!head) { head = tail = newNode; } else { tail->next = newNode; tail = newNode; } } std::cout << "Linked list before swapping pairwise: "; printLinkedList(head); swapPairs(head); std::cout << "Linked list after swapping pairwise: "; printLinkedList(head); // Clean up memory while (head) { Node* temp = head; head = head->next; delete temp; } return 0; } //awasthi

Imagine you are a teacher preparing seating arrangements for a classroom. You have a list of students' names, represented by a singly linked list. The linked list is arranged in a specific order, but you want to pair up the students in a different way for a group activity. To achieve this, you need to write a function that swaps elements pairwise in the linked list. Each pair of students will sit together during the activity, fostering collaboration and teamwork. By rearranging the linked list, you can create new pairs of students without changing their individual positions in the list. For example, if the linked list is 1->2->3->4->5 then the program should change it to 2->1->4->3->5. Note: This question is asked by Amazon, Microsoft, and Moonfrog Labs.

#include <iostream> struct Node { int data; Node* next; Node(int data) : data(data), next(nullptr) {} }; int calculateDecimalValue(Node* head) { int decimalValue = 0; Node* current = head; while (current != nullptr) { decimalValue = decimalValue * 2 + current->data; current = current->next; } return decimalValue; } void printLinkedList(Node* head) { Node* current = head; if (current == nullptr) { std::cout << "Empty linked list"; return; } while (current != nullptr) { std::cout << current->data << " "; current = current->next; } } int main() { int n; std::cin >> n; Node* head = nullptr; Node* tail = nullptr; for (int i = 0; i < n; ++i) { int value; std::cin >> value; Node* newNode = new Node(value); if (!head) { head = tail = newNode; } else { tail->next = newNode; tail = newNode; } } std::cout << "Linked List: "; printLinkedList(head); std::cout << std::endl; int decimalValue = calculateDecimalValue(head); std::cout << "Decimal Value: " << decimalValue << std::endl; // Clean up memory while (head) { Node* temp = head; head = head->next; delete temp; } return 0; } //awasthi

You are developing a smart device that reads binary data from sensors installed in various locations. Each sensor generates a stream of binary data, and the binary values are stored in a linked list. Your task is to implement a function that calculates the decimal value of the binary data represented by the linked list. The linked list represents the binary representation of a number, with the most significant bit at the head of the linked list. Your function should traverse the linked list and calculate the decimal value of the binary number. Note: This is a sample question asked in the Google interview.

// You are using GCC #include <iostream> class Node { public: int value; Node* next; Node(int val) : value(val), next(nullptr) {} }; Node* reverseKNodes(Node* head, int k) { Node* prev = nullptr; Node* current = head; Node* next_node = nullptr; int count = 0; while (current != nullptr && count < k) { next_node = current->next; current->next = prev; prev = current; current = next_node; count++; } if (next_node != nullptr) { head->next = reverseKNodes(next_node, k); } return prev; } void printLinkedList(Node* head) { Node* current = head; while (current != nullptr) { std::cout << current->value << " "; current = current->next; } std::cout << std::endl; } int main() { int N, value, k; std::cin >> N; Node* head = nullptr; Node* current = nullptr; for (int i = 0; i < N; ++i) { std::cin >> value; if (head == nullptr) { head = new Node(value); current = head; } else { current->next = new Node(value); current = current->next; } } std::cin >> k; // Print the original linked list std::cout << "Original Linked List: "; printLinkedList(head); // Reverse every k nodes head = reverseKNodes(head, k); // Print the modified linked list std::cout << "Modified Linked List: "; printLinkedList(head); // Clean up memory while (head != nullptr) { Node* temp = head; head = head->next; delete temp; } return 0; } //awasthi

You are working on a data processing system for a manufacturing company. The company has a production line where items are produced and each item is represented by a node in a linked list. The linked list represents the order in which the items are produced. Your task is to develop a module that can reverse the order of production for a specific number of items at a time. This will help in optimizing the production process by grouping and processing items in batches.

// Make the head of even sublist as the new head of the linked list head = evenHead; } }; // Define the main function int main() { // Declare a variable to store the number of elements in the linked list int n; // Read the input for n cin >> n; // Declare an object of the LinkedList class LinkedList list; // Use a loop to insert n elements at the beginning of the linked list for (int i = 0; i < n; i++) { // Declare a variable to store the input data for each node int data; // Read the input data for each node cin >> data; // Insert the node at the beginning of the linked list list.insertAtBeginning(data); } // Rearrange the nodes of the linked list such that even numbers come before odd numbers while maintaining their order within each group list.rearrangeList(); // Display the contents of the rearranged linked list list.displayList(); // Return zero to indicate successful termination of the program return 0; }

#include <iostream> using namespace std; // Define a class for the node class Node { public: int data; // Data of the node Node *next; // Pointer to the next node // Constructor to initialize the node with the given data and next pointer Node(int data, Node *next = NULL) { this->data = data; this->next = next; } }; // Define a class for the linked list class LinkedList { private: Node *head; // Pointer to the head of the linked list public: // Constructor to initialize the head pointer to NULL LinkedList() { head = NULL; } // Destructor to delete all the nodes of the linked list ~LinkedList() { Node *temp = head; while (temp != NULL) { Node *del = temp; temp = temp->next; delete del; } } // Method to insert a node at the beginning of the linked list void insertAtBeginning(int data) { // Create a new node with the given data Node *newNode = new Node(data); // Check if the linked list is empty if (head == NULL) { // Make the new node as the head of the linked list head = newNode; } else { // Make the new node point to the current head of the linked list newNode->next = head; // Make the new node as the new head of the linked list head = newNode; } } // Method to display the contents of the linked list void displayList() { // Check if the linked list is empty if (head == NULL) { cout << "Linked List is empty" << endl; } else { // Traverse the linked list from head to tail Node *temp = head; while (temp != NULL) { // Print the data of each node followed by a space cout << temp->data << " "; // Move to the next node temp = temp->next; } // Print a new line cout << endl; } } // Method to rearrange the nodes of the linked list such that even numbers come before odd numbers while maintaining their order within each group void rearrangeList() { // Check if the linked list is empty or has only one node if (head == NULL head->next == NULL) { return; // No need to rearrange } // Declare pointers to store the heads and tails of even and odd sublists Node *evenHead = NULL, *evenTail = NULL, *oddHead = NULL, *oddTail = NULL; // Traverse the original linked list from head to tail Node *temp = head; while (temp != NULL) { // Check if the current node has an even or odd data value if (temp->data % 2 == 0) { // Even case // Check if the even sublist is empty if (evenHead == NULL) { // Make the current node as the head and tail of the even sublist evenHead = evenTail = temp; } else { // Append the current node at the end of the even sublist and update its tail pointer evenTail->next = temp; evenTail = temp; } } else { // Odd case // Check if the odd sublist is empty if (oddHead == NULL) { // Make the current node as the head and tail of the odd sublist oddHead = oddTail = temp; } else { // Append the current node at the end of the odd sublist and update its tail pointer oddTail->next = temp; oddTail = temp; } } // Move to the next node in the original linked list temp = temp->next; } // Check if either of the sublists is empty if (evenHead == NULL oddHead == NULL) { return; // No need to rearrange further } // Concatenate the even and odd sublists and update their pointers accordingly // Make the tail of even sublist point to the head of odd sublist evenTail->next = oddHead; // Make the tail of odd sublist point to NULL oddTail->next = NULL;

You are tasked with creating a program that processes a linked list containing integer data and rearranges its nodes. Specifically, your program should separate the even and odd integers, placing the even integers before the odd ones while maintaining their original order within each group.

// You are using GCC #include <iostream> #include <list> #include <string> int main() { int n; std::cin >> n; std::list<std::string> document; for (int i = 0; i < n; ++i) { std::string line; std::cin >> line; document.push_front(line); } std::string appendedString; std::cin >> appendedString; // Printing the initial document content std::cout << "Document:"; for (const std::string& line : document) { std::cout << " " << line; } std::cout << std::endl; // Appending the given string to the document document.push_back(appendedString); // Printing the updated document content std::cout << "Updated Document:"; for (const std::string& line : document) { std::cout << " " << line; } std::cout << std::endl; return 0; } //awasthi

You are developing a text editor application that allows users to manage a document. The application uses a linked list data structure to represent the document content. Each node of the linked list contains a string representing a line of text. The application supports two operations: inserting new string values at the beginning of the document and appending a new string at the end of the document. If no input string list is created and if no value is appended to the list, then an empty list should be returned as output.

#include <stdio.h> #include <stdlib.h> // Define a structure for the node struct node { int data; // Data of the node struct node *next; // Pointer to the next node }; // Define a function to create a new node and return its pointer struct node *createNode(int data) { // Allocate memory for the node struct node *newNode = (struct node *)malloc(sizeof(struct node)); // Check if memory allocation is successful if (newNode == NULL) { printf("Memory allocation failed\n"); exit(1); } // Assign the data and the next pointer newNode->data = data; newNode->next = NULL; // Return the pointer to the new node return newNode; } // Define a function to insert a node at the beginning of the linked list and return its pointer struct node *insertAtBeginning(struct node *head, int data) { // Create a new node with the given data struct node *newNode = createNode(data); // Check if the linked list is empty if (head == NULL) { // Make the new node as the head of the linked list head = newNode; } else { // Make the new node point to the current head of the linked list newNode->next = head; // Make the new node as the new head of the linked list head = newNode; } // Return the pointer to the updated head of the linked list return head; } // Define a function to display the contents of the linked list void displayList(struct node *head) { // Check if the linked list is empty if (head == NULL) { printf("Linked List is empty\n"); } else { // Print the text "Linked List: " printf("Linked List: "); // Traverse the linked list from head to tail struct node *temp = head; while (temp != NULL) { // Print the data of each node followed by a space printf("%d ", temp->data); // Move to the next node temp = temp->next; } // Print a new line printf("\n"); } } // Define the main function int main() { // Declare a pointer to store the head of the linked list struct node *head = NULL; // Declare variables to store the input data and choice int data, choice; // Use a loop to insert nodes until choice is not equal to zero do { // Read the input data for the node scanf("%d", &data); // Insert the node at the beginning of the linked list and update the head pointer head = insertAtBeginning(head, data); // Print the message "Node inserted" on a new line printf("Node inserted\n"); // Read the input choice for continuing or ending insertion scanf("%d", &choice); } while (choice == 0); // Repeat until choice is zero // Display the contents of the linked list displayList(head); // Print the message "Node ended" on a new line printf("Node ended\n"); // Return zero to indicate successful termination of the program return 0; }

Kathir wants to create a program that allows him to build a linked list by inserting nodes at the beginning. He wants to be able to input the data for each node and specify when to stop inserting nodes (defined as 0). After inserting the nodes, he wants to display the contents of the linked list. Help Kathir by providing the required input and output formats for the code.

// You are using GCC #include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int value) { data = value; next = nullptr; } }; class LinkedList { public: Node* head; LinkedList() { head = nullptr; } void appendLeft(int value) { Node* new_node = new Node(value); new_node->next = head; head = new_node; } void appendRight(int value) { Node* new_node = new Node(value); if (!head) { head = new_node; return; } Node* current = head; while (current->next) { current = current->next; } current->next = new_node; } void display() { Node* current = head; while (current) { cout << current->data << " "; current = current->next; } } }; int main() { LinkedList linked_list; while (true) { int choice; cin >> choice; if (choice == 1) { int value; cin >> value; linked_list.appendLeft(value); } else if (choice == 2) { int value; cin >> value; linked_list.appendRight(value); } else if (choice == 3) { cout << "Linked List: "; linked_list.display(); cout << endl; } else if (choice == 4) { break; } else { cout << "Invalid choice" << endl; } } return 0; } //awasthi

Vijay wants to create a program that allows him to manipulate a linked list. He wants to be able to perform the following operations: 1: Append Left: Append a node at the beginning(left) of the linked list. 2: Append Right: Append a node at the end(right) of the linked list. 3: Print: Print the contents of the linked list. 4: Exit: Exit the program.

#include <iostream> #include <string> using namespace std; class Node { public: string data; Node* next; Node(string value) { data = value; next = nullptr; } }; class LinkedList { public: Node* head; LinkedList() { head = nullptr; } void append(string value) { Node* new_node = new Node(value); if (!head) { head = new_node; return; } Node* current = head; while (current->next) { current = current->next; } current->next = new_node; } void display() { Node* current = head; while (current) { cout << current->data << " "; current = current->next; } } }; int main() { int num_of_strings; cin >> num_of_strings; LinkedList linked_list; for (int i = 0; i < num_of_strings; ++i) { string value; cin >> value; linked_list.append(value); } string new_string; cin >> new_string; linked_list.append(new_string); cout << "Linked List Contents: "; linked_list.display(); cout << endl; return 0; } //awasthi

Jaanu wants to create a program that allows her to create a linked list of strings. Jaanu to enter the number of strings she wants to insert into the linked list. Then, she should enter each string one by one and insert them at the end of the linked list. After that, ask Jaanu to enter a new string, which will be appended at the end of the linked list. Finally, display the contents of the linked list.

📌UNIT -2 Answers DSA :——————

// You are using GCC #include <iostream> using namespace std; int main() { int n ,i ,j,k; cin>>n; int arr[n]; for(i=0;i<n;i++) { cin>>arr[i]; } cin>>k; for(i=0;i<n-1;i++) { int min=i; for(j=i+1;j<n;j++) { if(arr[j]<arr[min]) { min=j; } } if(min!=i) { swap(arr[i],arr[min]); } } cout<<"Sorted order: "; for(i=0;i<n;i++) { cout<<arr[i]<<" "; } cout<<endl; cout<<"The kth smallest element is : "; cout<<arr[k-1]; }