Naive Approach:

A naive approach could be to sort the linked list using any sorting algorithm, for example: Insertion Sort, Selection Sort, Merge Sort,etc. By this method the best time complexity you can achieve is O(nlogn).

Pseudo Code

MergeSort(headRef)

• Check for HEAD if its NULL then return
• Check if there is only one element in the Linked List then return
• Else divide the linked list into two halves
• Sort the two halves A and B

MergeSort(A);
MergeSort(B);

• Merge the sorted A and B and update the HEAD pointer

C++ Function Implementation

Node* SortedMerge(Node* a, Node* b) {
        Node* result = NULL;
        if (a == NULL)
                return (b);
        else if (b == NULL)
                return (a);
        if (a->data <= b->data) {
                result = a;
                result->next = SortedMerge(a->next, b);
        }
        else {
                result = b;
                result->next = SortedMerge(a, b->next);
        }
        return (result);
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
        Node* fast;
        Node* slow;
        slow = source;
        fast = source->next;

        while (fast != NULL) {
                fast = fast->next;
                if (fast != NULL) {
                        slow = slow->next;
                        fast = fast->next;
                }
        }

        *frontRef = source;
        *backRef = slow->next;
        slow->next = NULL;
}
void MergeSort(Node** headRef) {
        Node* head = *headRef;
        Node* a;
        Node* b;

        if ((head == NULL) || (head->next == NULL)) {
                return;
        }

        FrontBackSplit(head, &a, &b);

        MergeSort(&a);
        MergeSort(&b);

        *headRef = SortedMerge(a, b);
}

Optimised Approach

As you can see the sample I/O input list is sorted on absolute values but if you see closely all positive numbers are sorted in ascending order but negative numbers in descending order, we can take advantage of this fact. What we'll do is, we will traverse the LL and whenever we find a negative number or any number which is out of order, we will remove it from that position and insert it at the beginning of LL.

Pseudo Code

sortList(Node** head)

• Define two variables prev and curr
  • set prev to head pointer and curr next to head pointer
• Traverse the list to the end
  • If( curr < prev ) then remove curr from linked list and insert it at beginning

C++ Function Implementation

void sortList(Node** head){
    Node* prev = (*head);
    Node* curr = (*head)->next;

    while (curr != NULL) {

        if (curr->data < prev->data) {
            prev->next = curr->next;

            curr->next = (*head);
            (*head) = curr;

            curr = prev;
        }
        else{
            prev = curr;
        }

        curr = curr->next;
    }
}

Program Code

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    Node* next;
    int data;
};
// Optimised Approach
void sortList(Node** head){
        Node* prev = (*head);
        Node* curr = (*head)->next;

        while (curr != NULL) {

            if (curr->data < prev->data) {
                prev->next = curr->next;

                curr->next = (*head);
                (*head) = curr;

                curr = prev;
            }
            else{
                prev = curr;
            }

            curr = curr->next;
        }
}
//Naive Approach
Node* SortedMerge(Node* a, Node* b) {
        Node* result = NULL;
        if (a == NULL)
                return (b);
        else if (b == NULL)
                return (a);
        if (a->data <= b->data) {
                result = a;
                result->next = SortedMerge(a->next, b);
        }
        else {
                result = b;
                result->next = SortedMerge(a, b->next);
        }
        return (result);
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
        Node* fast;
        Node* slow;
        slow = source;
        fast = source->next;

        while (fast != NULL) {
                fast = fast->next;
                if (fast != NULL) {
                        slow = slow->next;
                        fast = fast->next;
                }
        }

        *frontRef = source;
        *backRef = slow->next;
        slow->next = NULL;
}
void MergeSort(Node** headRef) {
        Node* head = *headRef;
        Node* a;
        Node* b;

        if ((head == NULL) || (head->next == NULL)) {
                return;
        }

        FrontBackSplit(head, &a, &b);

        MergeSort(&a);
        MergeSort(&b);

        *headRef = SortedMerge(a, b);
}
void push(Node** head, int data)
{
    Node* newNode = new Node;
    newNode->next = (*head);
    newNode->data = data;
    (*head) = newNode;
}
Function to Print LL
void printList(Node* head)
{
    while (head != NULL)
    {
        cout << head->data;
        if (head->next != NULL)
            cout << " -> ";
        head = head->next;
    }
    cout<<endl;
}
int main(){

        Node* head = NULL;
        int t,n,temp;
        cin >> t;
        cin >> n;
        for(int i = 0; i < n; i++){
                cin >> temp;
                    push(&head, temp);
        }

        sortList(&head);
        //	MergeSort(&head);
        /*Uncomment MergeSort() to use Naive Approach*/

        printList(head);
        return 0;
}