include using namespace std struct node int val node next

#include <iostream>
using namespace std;

struct node {
int val;
node *next;
};

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 ->val << endl;
count++;
temp = temp->next;
}
}

void sortList(node **head) {
// your code here
}

int main() {
// Create an unsorted list:
node one, two, three, four, five;
one.val = 1;
two.val = 2;
three.val = 3;
four.val = 4;
five.val = 5;

// 2 -> 4 -> 1 -> 5 -> 3
node *head = &two;
two.next = &four;
four.next = &one;
one.next = &five;
five.next = &three; three.next = NULL;

// Unsorted List:
cout<<\"Unsorted List:\"<<endl;
printList(head);

// Sorted List:
sortList(&head);
cout<<\"Sorted List:\"<<endl;
printList(head);

return 0;
}

Note: I have bolded the function that needs to be completed.

The Problem 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 (eg: you should never use the new word, you must rearrange the memory that has already been allocated). 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 tests your sortList function

Solution

As per the given question we can have following code in which we can use bubble sort technique to sort the link list:

For your simplicty the above bolded function is given below as the rest code remains the same:

void sortList(node **head) {

}