0

I need to write a function splitMid that will split a linked list into two sublists of equal size. I have written most of the functions that I need to achieve this and some other things, but I am having trouble getting started on this function. Can anyone point me in the right direction please?

Here is what I have so far...

```
template<class Type>
bool linkedListType<Type>::isEmptyList()
{
return(first == NULL);
}
template<class Type>
linkedListType<Type>::linkedListType() // default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while(first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template<class Type>
int linkedListType<Type>::length()
{
return count;
} // end length
template<class Type>
Type linkedListType<Type>::front()
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template<class Type>
Type linkedListType<Type>::back()
{
assert(last != NULL);
return last->info; //return the info of the first node
}//end back
template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current; //pointer to traverse the list
bool found;
current = first; //set current to point to the
//first node in the list
found = false; //set found to false
while(current != NULL && !found) //search the list
if(current->info == searchItem) //item is found
found = true;
else
current = current->link; //make current point
//to the next node
return found;
}//end search
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
assert(newNode != NULL); //If unable to allocate memory,
//terminate the program
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
count++; //increment count
if(last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}
template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
assert(newNode != NULL); //If unable to allocate memory,
//terminate the program
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode
//to NULL
if(first == NULL) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual last node
count++; //increment count
}
}//end insertLast
//Overloading the stream insertion operator
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
nodeType<Type> *current; //pointer to traverse the list
current = list.first; //set current so that it points to
//the first node
while(current != NULL) //while more data to print
{
osObject<<current->info<<" ";
current = current->link;
}
return osObject;
}
template<class Type>
linkedListType<Type>::~linkedListType() // destructor
{
destroyList();
}//end destructor
template<class Type>
void linkedListType<Type>::splitMid(linkedListType<Type> &sublist)
{
}
```