# Absolute List Sorting

Last updated: 6th Sep, 2020

### Problem Statment

Given a linked list L of N nodes, sorted in ascending order based on the absolute values of its data. Sort the linked list according to the actual values.

#### Input

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case contains a positive integer N denoting the size of linked list. The second line of each test case contains N space separated integers denoting the values of N nodes.

#### Output

Corresponding to each test case, the expected output will be space separated values of the sorted linked list.

Example 1:

    Input : [1] -> [-2] -> [-3] -> [4] -> [-5]
    Output: [-5] -> [-3] -> [-2] -> [1] -> [4]

### 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;
    }