Home » Interview Questions » LinkedList Interview Questions » Sort linked which is sorted on absolute values

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

READ  Add two numbers

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions