Home » Interview coding problems/challenges

Absolute sorting on a single linked list

In this article, we are going to see how to sort a single linked list which is already sorted based on absolute value? This article has been featured in Amazon, Microsoft interview rounds. Submitted by Radib Kar, on April 20, 2019

Problem statement

Given a singly linked list which is ordered in terms of absolute value. Return the sorted linked list in ascending order (based on their original values). No additional storage should be used.

Example:

    Given the linked list: 1->2-> -3->4-> -5->NULL 
    After ordering based on original values output will be: 
    -5 -> -3 -> 1 ->2->4->NULL
    
    Given the linked list: 1->2->3->4->5->6->NULL 
    After ordering based on original values output will be: 
    1->2->3->4->5->6->NULL

Solution:

The problem can be solved using the following concept:

1. We will make two lists out of the single linked list, say list1 and list2.
2. list1 be the list of non-negative nodes as per their order. So list1 is sorted already.
3. list2 be the list of negative valued nodes as per their order. Since sorted according to absolute values, list2 is actually sorted in descending order. In the other sense reverse of list2 is sorted in ascending order.
4. Now we need to append list1 to the reversed list2.
5. This results in the original sorted list.

So the basic algorithm is:

1. Construct list1 & list2 from the original list.
2. Reverse the list2.
3. Append list1 to reverse (list2).
4. This results in the ordered list (ascending order).

1. Constructing list1 & list2 out of list

This can be done by traversing the list and checking node values. If the current node is a non-negative node, append it to the list1 else append it to the list2.

//posi: pointer to construct the List1
//nega: pointer to construct the List1
//store1: head to list1
//store2: head to list2
Node* posi=NULL,*nega=NULL;
    Node* store1=NULL,*store2=NULL;
    int countp=0,countn=0;
	
    while(temp){ //temp is the current node of original list
        if(temp->data>=0 && countp==0){//finding first node of list1
            posi=temp;
            store1=posi;
            countp++;
            temp=temp->next;
        }
        else if(temp->data>=0){//for other nodes of list1

            posi->next=temp;
            posi=posi->next;
            temp=temp->next;
        }
        else if(temp->data<0 && countn==0){//finding first node of list2
            nega=temp;
            store2=nega;
            countn++;
            temp=temp->next;
        }
        else if(temp->data<0){ //for other nodes of list2

            nega->next=temp;
            nega=nega->next;
            temp=temp->next;
        }
    }
    if(posi)
    posi->next=NULL;

    if(nega)
    nega->next=NULL;

2. Reverse the list2 //If list2 is constructed then only

So the list has been split to list1 and list2 ( store1 and store2 be their respective heads),

Now, we need to reverse the list2. It's pretty much similar as we did in reverse a single linked list.

Pre-requisites:

• *prev - to store the previous node which will become ultimately the next node after reversal for current node.
• *cur - to store the current node.
• *next - to store the next node which will become current node in the next iteration.
• Initialize *prev & *next to NULL, *cur to head.

    while(cur!=NULL)
        Set *nextto cur->next
        Set cur->nextto *prev
        Set *prev to *cur
        Set *cur to *next
    End While loop

    Set head to *prev

3. Appending list1 to reversed list2 //if list2 exists

Traverse list1 and append list2 at the end.

    IF(store2) //list2 exists
        store2=reverse(store2); //reverse list2
        *head=store2; //now head is the head to the output list

        While(store2->next){ //traverse reversed list2
            store2=store2->next;
        END While

        //append list1(list1 can  be NULL also if no such list1 created)
        store2->next=store1; 
    Else //if list2 doesn’t exist
        *head=store1; //list1 will be the result
    END IF-ELSE

Example with explanation:

    Input:
    1 -> 2 -> -3 -> 4 -> -5
    
    After splitting:

    List1: 1 -> 2 -> 4 -> NULL
    List2: -3 -> -5-> NULL

    Reversing list2:
    - 5-> -3 -> NULL

    Appending list1:
    -5 -> -3 -> 1 -> 2 -> 4 -> NULL

    For example2, List2 doesn't exist.
    Output will be only list1

C++ Implementation

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

class Node{
    public:
	int data; // data field
	Node *next;
};

void display(Node* head){
	Node* current=head; // current node set to head
	while(current!=NULL){ //traverse until current node isn't NULL
		printf("%d ",current->data);
		current=current->next; // go to next node
	}
}

Node* creatnode(int d){
	Node* temp=(Node*)malloc(sizeof(Node));
	temp->data=d;
	temp->next=NULL;
	return temp;
}

Node* reverse(Node* head){
    
    Node* next=NULL,*prev=NULL,*current;
    
    current=head;
    
    
    while(current!=NULL){
        
        next=current->next;
        current->next=prev;
        prev=current;
        current=next;
        
    }
    
    return prev;
        
}
void sortList(Node** head)
{
    
    
    Node* temp=*head;
    //base case
    if(!temp || !temp->next)
    return ;
    
    Node* posi=NULL,*nega=NULL;
    Node* store1=NULL,*store2=NULL;
    int countp=0,countn=0;
	//absolute sorting
    while(temp){
        if(temp->data>=0 && countp==0){
            posi=temp;
            store1=posi;
            countp++;
            temp=temp->next;
        }
        else if(temp->data>=0){
            
            posi->next=temp;
            posi=posi->next;
            temp=temp->next;
        }
        else if(temp->data<0 && countn==0){
            nega=temp;
            store2=nega;
            countn++;
            temp=temp->next;
        }
        else if(temp->data<0){
            
            nega->next=temp;
            nega=nega->next;
            temp=temp->next;
        }
    }
    if(posi)
    posi->next=NULL;
    if(nega)
    nega->next=NULL;
    if(store2){
        store2=reverse(store2);
    
        *head=store2;
    
        while(store2->next){
            store2=store2->next;
        }
    
        store2->next=store1;
    }
    else
    *head=store1;
    
    
}
int main(){
	printf("creating the linked list by inserting new nodes at the end\n");
	printf("enter 0 to stop building the list, else enter any integer\n");
	int k,count=1,x;
	Node* curr,*temp;
	scanf("%d",&k);
	Node* head=creatnode(k); //buliding list, first node
	scanf("%d",&k);
	temp=head;

	///////////////////inserting at the end//////////////////////
	while(k){
		curr=creatnode(k);
		temp->next=curr;//appending each node
		temp=temp->next;
		scanf("%d",&k);
	}
	cout<<"before absolute value sorting...\n";
	display(head); // displaying the list
	cout<<"\nafter absolute sorting...\n";
	sortList(&head);
	display(head);
	return 0;
}

Output

First run:
creating the linked list by inserting new nodes at the end 
enter 0 to stop building the list, else enter any integer
1 2 -3 4 -5 0
before absolute value sorting... 
1 2 -3 4 -5
after absolute sorting...
-5 -3 1 2 4 

Second run:
creating the linked list by inserting new nodes at the end 
enter 0 to stop building the list, else enter any integer
1 2 3 4 5 6 0
before absolute value sorting... 
1 2 3 4 5 6
after absolute sorting...
1 2 3 4 5 6