//MAIN FUNCTION

#include #include "LinkedList.h"

int main(int argc, const char * argv[]) { std::cout << "Hello, World! "; LinkedNode* head = new LinkedNode(100); LinkedNode* lastNode = head; for (int i=99; i>=0; i--) { LinkedNode* node = new LinkedNode(i); lastNode->setNext(node); lastNode = node; } lastNode->setNext(nullptr); // print elements in the list cout << "*** Origional List ***"<< endl; head->printList(); // sort the list cout << "Performing Sort..."<< endl<doMergeSort(&head); // now, list should be sorted... cout << "*** Sorted List ***"<< endl; head->printList(); return 0; }

include // Include the string library.

#include // Include to manipulate files.

#include // Include to use stringstream.

#include

#include

#include

using namespace std;

#ifndef LinkedList_h

#define LinkedList_h

#endif /* LinkedList_h */

// need compar function so we can swap generic things

template

class LinkedNode

{

protected:

// link to next node

LinkedNode *next = nullptr;

T nodeValue;

int nodeKey=0;

void splitList(LinkedNode *head, LinkedNode **first, LinkedNode **second);

LinkedNode* mergeLists(LinkedNode *first, LinkedNode *second);

void swapNodes(LinkedNode **node1, LinkedNode **node2);

public:

//ctor

LinkedNode(T value,

LinkedNode *next_node=nullptr,

int key=0)

{

next= next_node;

nodeValue = value;

nodeKey = key;

}

// ** Getters **

const T getValue() {return nodeValue;}

//read-only node key

const int getKey() {return nodeKey;}

// link to next node

LinkedNode *getNext() {return next;}

// ** Setters **

void setNext(LinkedNode *next_node) {next = next_node;

// Prints all items in the list,

// starting from current node.

void printList();

// returns a reference to the nth node in the list

LinkedNode *getNthNode(int n);

// performs a merge sort, and returns new head

void doMergeSort();

void doMergeSort(LinkedNode **head);

};

Do not need to implement all of the functions. Please implement the following functions so that the merge sort works, including

doMergeSort()

doMergeSort(LinkedNode ** head)

splitList(LinkedNode *head, LinkedNode **first, LinkedNode **second)

LinkedNode* mergeLists(LinkedNode *first, LinkedNode *second);

void printList();