Please answer in C++ programming language!

Complete the sortList function that accepts a Node ** (the head of a linked list, passed by pointer). This function must sort the linked list without allocating any nodes and without changing what's in the data_ member variables. In other words, you are to sort the list only by manipulating the pointers.

This sort does not need to be the most efficient sort possible, it just needs to be correct. A main function has been provided that exercises your sortList function.

main.cpp:

#include

#include "Node.h"

using namespace std;

void printList(Node *head) {

if (head == NULL) {

cout << "Empty list" << endl;

return;

}

Node *temp = head;

int count = 0;

while(temp != NULL) {

cout << "Node " << count << ": " << temp ->data_ << endl;

count++;

temp = temp->next_;

}

}

int main() {

// Create an unsorted list:

Node one, two, three, four, five;

one.data_ = 1;

two.data_ = 2;

three.data_ = 3;

four.data_ = 4;

five.data_ = 5;

cout << Node::getNumNodes() << endl;

// 2 -> 4 -> 1 -> 5 -> 3

Node *head = &two;

two.next_ = &four;

four.next_ = &one;

one.next_ = &five;

five.next_ = &three;

three.next_ = NULL;

cout << Node::getNumNodes() << endl;

// Unsorted List:

cout<<"Unsorted List:"<

printList(head);

// Sorted List:

sortList(&head);

cout<<"Sorted List:"<

printList(head);

cout << Node::getNumNodes() << endl;

return 0;

}

Node.h:

#ifndef NODE_H

#define NODE_H

#include

using namespace std;

class Node {

public:

int data_;

Node *next_;

Node();

Node(Node &other);

~Node();

static int getNumNodes() {

return numNodes;

}

private:

static int numNodes;

};

void sortList(Node **head);

#endif

Node.cpp:

#include "Node.h"

using namespace std;

void sortList(Node **head) {

// your code here!

}

Node::Node() {

numNodes++;

}

Node::Node(Node &other) {

this->data_ = other.data_;

this->next_ = other.next_;

numNodes++;

}

Node::~Node() {

numNodes--;

}

int Node::numNodes = 0;