Populate next higher in a singly linked list

Problem

/*
   Algo:  This is similar to insertion sort algorithm
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct node {

int data;
struct node *next;
struct node *next_higher;

}Node;


typedef Node *List;


List populateNextHigher(List l) {

if(!l) return NULL;

Node *start = l; //starting of the sorted list
l = l->next;

while(l){ //iterate through the list

if(l->data < start->data){

l->next_higher = start;
start = l;

} else {

Node *p = start;

while(p->next_higher && l->data >= p->next_higher->data) //find the position of l
p = p->next_higher;

l->next_higher = p->next_higher; //insert l
p->next_higher = l;

}
l = l->next;
}

return start;
}


//Utilities

Node *makeNode(int n) {
Node *node = calloc(1, sizeof(Node));

node->data = n;
}

List array2List(int a[], int n){

List l = NULL;

if(n > 0) {
Node *end = l = makeNode(a[0]);
int i;

for(i = 1; i < n; ++i) {

end->next = makeNode(a[i]);
end = end->next;
}
}

return l;

}


void printList(List l) {

while(l){
printf("%d ", l->data);
l = l->next_higher;
}

printf("\n");
}

int main(){

int a[] = {90, 80, 60, 70, 50, 40,100};

List l = array2List(a, sizeof(a)/sizeof(int));

List h = populateNextHigher(l);
printList(h);

return 0;
}
Advertisements

One thought on “Populate next higher in a singly linked list

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s