# Absolute sorting on a single linked list

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

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

```

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

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

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* next=NULL,*prev=NULL,*current;

while(current!=NULL){

next=current->next;
current->next=prev;
prev=current;
current=next;

}

return prev;

}
{

//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);

while(store2->next){
store2=store2->next;
}

store2->next=store1;
}
else

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

///////////////////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";
cout<<"\nafter absolute sorting...\n";
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
```

TOP Interview Coding Problems/Challenges

Learn PCB Designing: PCB DESIGNING TUTORIAL

 Recommended posts C Tips & Tricks, C++ Tips & Tricks Introduction to Linux (Its modes, Safety, Most popular Applications) Linux Best Distros of 2018 C programming optimization techniques Differences b/w C & Embedded C? Embedded C Interview Q. & A. C programming tips for Embedded Development Basic rules of writing a C program Important points (rules) to remember while writing C/C++ program Top 5 Websites for solving programming challenges Read more...

 Others... Computer G.K. (MCQ) Most viewed pages... Categories...

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates