#include #include #include using namespace std; class SinglyLinkedListNode { public: int data; SinglyLinkedListNode *next; SinglyLinkedListNode(int node_data) { this->data = node_data; this->next = nullptr; } }; class SinglyLinkedList { public: SinglyLinkedListNode *head; SinglyLinkedListNode *tail; SinglyLinkedList() { this->head = nullptr; this->tail = nullptr; } void insert_node(int node_data) { SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data); if (!this->head) { this->head = node; } else { this->tail->next = node; } this->tail = node; } }; void print_singly_linked_list(SinglyLinkedListNode* node, string sep, ofstream& fout) { while (node) { fout << node->data; node = node->next; if (node) { fout << sep; } } } void free_singly_linked_list(SinglyLinkedListNode* node) { while (node) { SinglyLinkedListNode* temp = node; node = node->next; free(temp); } } // Complete the mergeLists function below. /* * For your reference: * * SinglyLinkedListNode { * int data; * SinglyLinkedListNode* next; * }; * */ SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { if (head1 == nullptr) { return head2; } if (head2 == nullptr) { return head1; } auto head_new = head1; if (head_new->data > head2->data) { head_new = head2; head2 = head2->next; } else { head1 = head1->next; } auto iter = head_new; while (1) { if (head1 == nullptr) { iter->next = head2; break; } if (head2 == nullptr) { iter->next = head1; break; } if (head1->data <= head2->data) { iter->next = head1; head1 = head1->next; } else { iter->next = head2; head2 = head2->next; } iter = iter->next; } return head_new; } int main() { ofstream fout(getenv("OUTPUT_PATH")); int tests; cin >> tests; cin.ignore(numeric_limits::max(), '\n'); for (int tests_itr = 0; tests_itr < tests; tests_itr++) { SinglyLinkedList* llist1 = new SinglyLinkedList(); int llist1_count; cin >> llist1_count; cin.ignore(numeric_limits::max(), '\n'); for (int i = 0; i < llist1_count; i++) { int llist1_item; cin >> llist1_item; cin.ignore(numeric_limits::max(), '\n'); llist1->insert_node(llist1_item); } SinglyLinkedList* llist2 = new SinglyLinkedList(); int llist2_count; cin >> llist2_count; cin.ignore(numeric_limits::max(), '\n'); for (int i = 0; i < llist2_count; i++) { int llist2_item; cin >> llist2_item; cin.ignore(numeric_limits::max(), '\n'); llist2->insert_node(llist2_item); } SinglyLinkedListNode* llist3 = mergeLists(llist1->head, llist2->head); print_singly_linked_list(llist3, " ", fout); fout << "\n"; free_singly_linked_list(llist3); } fout.close(); return 0; }