Examples and Exercises on Linked Lists:1. BuildOneTwoThree() FunctionHere is simple function which uses pointer operations to build the list {1, 2, 3}. Thisfunction demonstrates how calls to malloc() and pointer assignments (=) work to build apointer structure in the heap./*Build the list {1, 2, 3} in the heap and store its head pointer in a local stack variable. returns the head pointer to the caller.*/struct node* BuildOneTwoThree() {struct node* head = NULL;struct node* second = NULL;struct node* third = NULL;head = malloc(sizeof(struct node)); // allocate 3 nodes in the heapsecond = malloc(sizeof(struct node));third = malloc(sizeof(struct node));head->data = 1; // setup first nodehead->next = second; // note: pointer assignment rulesecond->data = 2; // setup second nodesecond->next = third;third->data = 3; // setup third linkthird->next = NULL;// At this point, the linked list referenced by "head"// matches the list in the drawing.return head;}ExerciseQ: Write the code with the smallest number of assignments (=) which will build theabove memory structure. - It requires 3 calls to malloc(). - 3 int assignments (=) to setup the ints. - 4 pointer assignments to setup head and the 3 next fields. With a little cleverness and knowledge of the C language, this can all be done with 7assignment operations (=).2. Length() FunctionThe Length() function takes a linked list and computes the number of elements in the list.Length() is a simple list function./* Given a linked list head pointer, compute and return the number of nodes in the list. */int Length(struct node* head) {struct node* current = head;int count = 0;while (current != NULL) {count++;current = current->next;}return count;}Exercisevoid LengthTest() {struct node* myList = BuildOneTwoThree();int len = Length(myList); // results in len == 3}What if we said head = NULL; at the end of Length() — would that mess up the myListvariable in the caller? Ans: No. head is a local which was initialized with a copy of the actual parameter, butchanges do not automatically trace back to the actual parameter. Changes to the localvariables in one function do not affect the locals of another function.ExerciseQ: What if the passed in list contains no elements, does Length() handle that caseproperly? Ans: Yes. The representation of the empty list is a NULL head pointer. TraceLength() on that case to see how it handles it.3. Correct Push() CodeThe list is passed via a pointer to the head pointer. In the code, this amounts to use of '&'on the parameter in the caller and use of '*' on the parameter in the callee. Inside Push(),the pointer to the head pointer is named "headRef" instead of just "head" as a reminderthat it is not just a simple head pointer./* Takes a list and a data value. Creates a new link with the given data and pushes it ontothe front of the list. The list is not passed in by its head pointer. Instead the list is passedin as a "reference" pointer to the head pointer -- this allows us to modify the caller'smemory. */void Push(struct node** headRef, int data) {struct node* newNode = malloc(sizeof(struct node));newNode->data = data;newNode->next = *headRef; // The '*' to dereferences back to the real head*headRef = newNode; // ditto}void PushTest() {struct node* head = BuildTwoThree();// suppose this returns the list {2, 3}Push(&head, 1); // note the &Push(&head, 13);/* head is now the list {13, 1, 2, 3} */}4. CopyList() Consider a CopyList() function that takes a list and returns a complete copy of that list.One pointer can iterate over the original list in the usual way. Two other pointers can keeptrack of the new list: one head pointer, and one tail pointer which always points to the lastnode in the new list. The first node is done as a special case, and then the tail pointer isused in the standard way for the others...struct node* CopyList(struct node* head) {struct node* current = head; // used to iterate over the original liststruct node* newList = NULL; // head of the new liststruct node* tail = NULL; // kept pointing to the last node in the new listwhile (current != NULL) {if (newList == NULL) { // special case for the first new nodenewList = malloc(sizeof(struct node));newList->data = current->data;newList->next = NULL;tail = newList;}else {tail->next = malloc(sizeof(struct node));tail = tail->next;tail->data = current->data;tail->next = NULL;}current = current->next;}return(newList);}Problems:1. Given a list and an index, return the data in the nth node of the list. The nodes are numbered from 0. Assert fails if the index is invalid (outside 0..lengh-1). int GetNth(struct node* head, int index) {// Your code}2. Write a function DeleteList() that takes a list, deallocates all of its memory and sets itshead pointer to NULL (the empty list). Hint: Use pointer to the head pointer 3. A more general version of Push(). Given a list, an index 'n' in the range 0..length, and adata element, add a new node to the list so that it has the given index.void InsertNth(struct node** headRef, int index, int data) {// your code...}4. Write a SortedInsert() function which given a list that is sorted in increasing order, anda single node, inserts the node into the correct sorted position in the list. While Push()allocates a new node to add to the list, SortedInsert() takes an existing node, and justrearranges pointers to insert it into the list. void SortedInsert(struct node** headRef, struct node* newNode) {// Your code...}5. Write an Append() function that takes two lists, 'a' and 'b', appends 'b' onto the end of'a', and then sets 'b' to NULL (since it is now trailing off the end of 'a').void Append(struct node** aRef, struct node** bRef) {/* Your code...*/}6. Given a list, split it into two sublists — one for the front half, and one for the back half.If the number of elements is odd, the extra element should go in the front list. SoFrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}. Getting this right for all the cases is harder than it looks. You should check yoursolution against a few cases (length = 2, length = 3, length=4) to make sure that the listgets split correctly near the short-list boundary conditions. If it works right for length=4,it probably works right for length=1000. You will probably need special case code to dealwith the (length <2) cases./* Split the nodes of the given list into front and back halves, and return the two listsusing the reference