Write a function that starts with a single linked list of items and a special value called thesplitting value. Two item values can be compared using the < operatorbut the items of the original linked list are in no particular order. The procedure divides the nodes into two linked lists: one containing all the nodes that contain an item less than the splitting value, and one that contains all the other nodes. If the original linked list had any repeated integers (i.e., any two or more nodes with the same item in them) then the new linked list that has this item should have the same number of nodes that repeat this item. It does not matter whether you preserve the original linked list or destroy it in the process of building the two new lists, but your comments should document what happens to the original linked list.

c++

Please use the given file, and provide sample test as well

// FILE: node1.h // PROVIDES: A class for a node in a linked list, and list manipulation // functions, all within the namespace main_savitch_5 

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); } 

// 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 using namespace std; namespace main_savitch_5 { 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(); } } }