## 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;
if(*head == 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
*head=current;
}
//O(1) constant time
}
//display linked list
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;
}
void SortLL(struct LLNode** head)
{
//Initialize
struct LLNode* previous = *head;
struct LLNode* current = (*head)->next;
//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;
current->next = *head;
*head = current;
//update current
current = previous;
}
else //Move forward if current is greater than previous
{
previous = current;
}
//Move forward
current = current->next;
}
}
//Main function
int main()
{
struct LLNode* head = NULL;
insertAtBeginning(&head, -10);
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 8);
insertAtBeginning(&head, -7);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, -5);
cout<<"Input linked list is: ";
display(&head);
SortLL(&head);
cout<<"\nFinal Sorted list is: ";
display(&head);
return 0;
}
```