(c++)Write a function that takes a linked list of integers and rearranges the nodes so that the integers stored are sorter into the order smallest to largest, with the smallest integer inn the node at the head of the list. If the original list had any integers occuring more than once, then the changed list will have the same number of each integer. For correctness you will use lists of integers but your function should still work if you replace the integer type with any other type for which the less than operation is partt of a total order semantics. use the following function prototype and specification:

void sort_list(node*& head_ptr);

//precondition: head_ptr is a head pointer of a linked list of items, and these items can be compared with a less-than //operator.

//Postcondition: head_ptr points to the head of a lilnked list with exaclty the same entries (including repetitions, if any), //but the entries in this list are sorted from smallest to largest. The original linked list is no longer available.

your procedure will implement the following algorithm (which is ofte caled selection sort): The algorithm removes nodes one at a time from the original list and adds the nodes to a second list until all the nodes have been moved to the second list. The second list will then be sorted.

//Pseudocode foe selection sort

while (the first list still has some nodes)

{

1. find the node with the largest item of all the nodes in the first list.

2. Remove ths node from the first list.

3. Insert this node at the head of the second list.

}

After all the nodes are moved to the second list, the pointer, head_ptr, can be moved to point t the head of the second list. Note that your function will move entire nodes, not just items, to the second list. Thus, the first list will get shorter and shorter until it is an empty list. Your function should not need to call the new operator since it is just mocing nodes from one list to another (not creating new nodes).

Here is the node file I already have and header file:

// FILE: node1.cxx // IMPLEMENTS: The functions of the node class and the // linked list toolkit (see node1.h for documentation). // INVARIANT for the node class: // The data of a node is stored in data_field, and the link in link_field.

#include "node1.h" #include // Provides assert #include // Provides NULL and size_t #include using namespace std;

size_t list_length(const node *head_ptr) // Library facilities used: cstdlib { const node *cursor; size_t answer;

answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) ++answer;

return answer; }

void list_head_insert(node *&head_ptr, const node::value_type &entry) { head_ptr = new node(entry, head_ptr); }

void list_insert(node *previous_ptr, const node::value_type &entry) { node *insert_ptr;

insert_ptr = new node(entry, previous_ptr->link()); previous_ptr->set_link(insert_ptr); }

node *list_search(node *head_ptr, const node::value_type &target) // Library facilities used: cstdlib { node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) if (target == cursor->data()) return cursor; return NULL; }

const node *list_search(const node *head_ptr, const node::value_type &target) // Library facilities used: cstdlib { const node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) if (target == cursor->data()) return cursor; return NULL; }

node *list_locate(node *head_ptr, size_t position) // Library facilities used: cassert, cstdlib { node *cursor; size_t i;

assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link(); return cursor; }

const node *list_locate(const node *head_ptr, size_t position) // Library facilities used: cassert, cstdlib { const node *cursor; size_t i;

assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link(); return cursor; }

void list_head_remove(node *&head_ptr) { node *remove_ptr;

remove_ptr = head_ptr; head_ptr = head_ptr->link(); delete remove_ptr; }

void list_remove(node *previous_ptr) { node *remove_ptr;

remove_ptr = previous_ptr->link(); previous_ptr->set_link(remove_ptr->link()); delete remove_ptr; }

void list_clear(node *&head_ptr) // Library facilities used: cstdlib { while (head_ptr != NULL) list_head_remove(head_ptr); }

void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr) // Library facilities used: cstdlib { head_ptr = NULL; tail_ptr = NULL;

// Handle the case of the empty list. if (source_ptr == NULL) return;

// Make the head node for the newly created list, and put data in it. list_head_insert(head_ptr, source_ptr->data()); tail_ptr = head_ptr;

// Copy the rest of the nodes one at a time, adding at the tail of new list. source_ptr = source_ptr->link(); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data()); tail_ptr = tail_ptr->link(); source_ptr = source_ptr->link(); } }

void list_print(node * head_ptr) { for(node *i = head_ptr; i != NULL; i = i->link()) { cout<data()<<" "; } cout<

//Header file

// FILE: node1.h // PROVIDES: A class for a node in a linked list, and list manipulation

#ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H

#include // Provides size_t and NULL

class node { public: // TYPEDEF typedef double value_type;

// CONSTRUCTOR node( const value_type &init_data = value_type(), node *init_link = NULL ) { data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields: void set_data(const value_type &new_data) { data_field = new_data; }

void set_link(node *new_link) { link_field = new_link; }

// Constant member function to retrieve the current data: value_type data() const { return data_field; }

// Two slightly different member functions to retreive // the current link: const node *link() const { return link_field; }

node *link() { return link_field; }

private: value_type data_field; node *link_field; };

// FUNCTIONS for the linked list toolkit std::size_t list_length(const node *head_ptr);

void list_head_insert(node *&head_ptr, const node::value_type &entry);

void list_insert(node *previous_ptr, const node::value_type &entry);

node *list_search(node *head_ptr, const node::value_type &target);

const node *list_search (const node *head_ptr, const node::value_type &target);

node *list_locate(node *head_ptr, std::size_t position);

const node *list_locate(const node *head_ptr, std::size_t position);

void list_head_remove(node *&head_ptr);

void list_remove(node *previous_ptr);

void list_clear(node *&head_ptr);

void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr); void list_print(node * head_ptr); void removeDuplicates(node * head);

#endif