# Sort linked which is sorted on absolute values

## Write a function to sort a given linked list which is already sorted based on absolute values.

### Example Time complexity : O(n)

## Algorithm

a. Traverse in the list till the end.

b. Store previous and current node.

c. If current is less than previous move it to beginning by detaching it from the list.

d. Else, make previous as current and move current.

### Algorithm working ## C++ Program

```#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
int data;
struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* current = new LLNode;
current->data = dataToBeInserted;
current->next = NULL;
*head=current; //if this is first node make this as head of list

else
{
current->next=*head; //else make the current (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
{
if (temp->data < 0)
{
cout<<"("<<temp->data<<")"<<"->";
}
else
{
cout<<temp->data<<"->";
}
}
else
{
if (temp->data < 0)
{
cout<<"("<<temp->data<<")";
}
else
{
cout<<temp->data;
}
}
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

{
//Initialize

//Traverse till the end (Till current equal to Null)
while (current != NULL)
{
//If current is smaller than previous
//Move current to begining
if (current->data < previous->data)
{
//detaching current
previous->next = current->next;
//update current
current = previous;
}
else //Move forward if current is greater than previous
{
previous = current;
}
//Move forward
current = current->next;
}
}

//Main function
int main()
{