*Note* All linked lists are null-terminated and singly linked. Input lists may
be empty, unless otherwise stated. If new nodes may be created, then
report whether or not space was exhausted, using a boolean reference
parameter.

Answer each question with a C++ subroutine.

**Insert in order**Given a linked list of integers sorted from smallest (at the head end) to largest, and a pointer to a single node containing an integer, insert the node in the linked list so that it remains sorted. (solution)**Cumulative sum**Given a null-terminated linked list,`in`, create a new null-terminated linked, list`out`, of the same length, such that node*i*of`out`contains the sum of the data in`in`'s nodes up to and including node*i*of list`in`. Detect heap exhaustion and report it by setting a boolean variable. (solution)**Delete last node**Given a nonempty list, delete the last node and set the new last link to null. (solution)**Deal**Given a null terminated linked list, rearrange its nodes into two lists: <first node, third node, fifth node, ...> and <second node, fourth node, sixth node, ...>. Do not allocate any new nodes. (solution)-
**Rifle Shuffle**Given two null terminated linked lists, combine their nodes so that the nodes of the new list alternate between those of the two original nodes: <first node of first list, first node of second list, second node of first list, second node of second list, ... >. Do not allocate any new nodes. **Catenate**Given two null-terminated linked lists headed by`left`and`right`, set the last link of the left list to point to the right list, thus joining them into one list. Do not allocate any new nodes.-
**Reverse**Given a null-terminated linked lists headed reverse the order of its nodes. Do not allocate any new nodes. **Read a list**Given a nonnegative integer*i*, read*i*integers from the input and build a null-terminated linked list such that the first integer in the input is the first node and so forth. Detect heap exhaustion and report it by setting a boolean variable.**List to int**Given a null-terminated linked list of integers from 0 to 9 (inclusive) representing a nonnegative integer in decimal (least significant digit at the head), compute into an`unsigned`variable, the integer that it represents. (The empty list represents 0.) You may assume that the list represents a number that can be represented by an`unsigned`.**Int to list**Given an non-negative integer , create a null-terminated linked list of integers between 0 and 9 representing the integer (least significant digit first). (0 is represented by an empty list.) Set a boolean variable to indicate whether or not space has been exhausted. Hint. In C++`i/10`, where i is an integer expression, gives the integer quotient of i divided by 10, and`i%10`gives the remainder.