Do according to question Dont use built in functions Dont use anything globally Create your own stack and queue if needed Dont use built in stack and queue. Do in c++ language
Extracted text: Question 2: Task is to update the previously implemented Single linked list by following functions using the following Node definition for all problems: class Node Item data; Node *next; Note: The head pointer of LinkedList class is publicly accessible 1. Write a function to concatenate two linked lists. Given lists 11 = (2, 3, 1) and 12 = (4, 5), after return from concatenate(11,12) the list 11 should be changed to be 11 = (2, 3, 1, 4, 5). Your function should not change 12 and should not directly link nodes from 1l to 12 (i.e. the nodes inserted into 11 should be copies of the nodes from 12.) void concatenate(Node & hl, Node* h2 ): // // Precondition: hl and h2 are head pointers of linked lists. I/ The lists may be empty or non-empty. // // Postcondition: A copy of list h2 is concatenated (added to the end) of list hl. List h2 should be unchanged by the function. // NOTE: The nodes added to the list hl must be copies of the I/ nodes in list h2. 2. Write a function to insert a number into a sorted linked list. Assume the list is sorted from smallest to largest value. After insertion, the list should still be sorted. Given the list 11 = (3, 17, 18, 27) and the value 20, on return 11 be the list (3, 17, 18, 20, 27). void insertInOrder(Node*& head_ptr, int value); // // Precondition: head_ptr is the head pointer of a linked list I/ sorted in non-decreasing order. The list may be empty or non-empty. // Postcondition: The number value is inserted in the list. // The list should be sorted on return from the function. 3. Write a function to return the median value in a sorted linked list. If the length i of the list is odd, then the median is the ceiling(i/2) member. For example, given the list (1, 2, 2, 5, 7, 9, 11) as input, your function should return the value 5. If the length of the list is even, then the median is the mean of the i/2 and (i/2)+1 members. Thus, the median of the sorted list (2, 4, 8, 9) is (4+8)/2. Finally, define the median of an empty list to be 0. 4. Write a function to reverse the nodes in a linked list. Your function should have time complexity O(n), where n is the length of the list. You should create no new nodes, void reverse(Node"& head_ptr); // Precondition: head_ptr is the head pointer of a linked list. // The list may be empty or non-empty. I/ Postcondition: head_ptr points to the list of Nodes in reverse I/ order.