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

it will be good if u can briefly describe logic in the beginning