5.8 Sort Linked List

Use mergersort to sort a linked list Do not use the following libraries: algorithm, cmath. Do not load the values into a vector and sort them. The sort must be done with a linked list Example Two lists 6->3->1->2->4->5 will return a list with 1->2->3->4->5->6. Input There will be no input read in anymore. Going forward use the hard-coded input on the template and ensure the program works. There will be one compare output test based on the hard-coded input. The rest of the tests will be unit tests. Output Print out the newly returned list. Just print out the integers separated by a space.

#include

#include

// DO NOT MODIFY

struct Node {

int val;

Node * next;

Node( int num ){

val = num;

next = nullptr;

}

};

// DO NOT MODIFY

Node * createList( std::vector & vec ){

int i = 0;

Node * head = new Node( vec[i++] );

Node * runner = head;

for( i; i < vec.size(); i++ ){

Node * temp = new Node( vec[i] );

runner->next = temp;

runner = runner->next;

}

return head;

}

Node* mergeTwoLists(Node* l1, Node* l2) {

// Use your mergeTwoLists function from last week

}

Node * mergeSort( Node * head ){

/* Follow merge sort. The tricky part is spliting the lists in half at each step correctly.

If you are not confident, draw out how you could split each list in half till you hit a base case.

*/

}

int main(){

// Just concentrate on the function

std::vector values{ 6, 3, 1, 2, 4, 5};

Node * list = createList( values );

list = mergeSort( list );

while( list ){

std::cout << list->val << " ";

list = list->next;

}