OrderedListUsingDoublePointer.c

// can also be implemented using functions which return the altered head of the list
struct node { 
  int val; 
  struct node* next; 
};

struct node** init() {
  struct node** l = malloc(sizeof(struct node*));
  *l = NULL;

  return p;
}

int getFirst(struct node** l) { 
  // If *l is NULL, the list is empty 
  if (*l == NULL) return -1; 
  else return (*l)->val; 
}

void insert(struct node** l, int x) { 
  struct node* p; 
  struct node* q; 
  
  // insertion at first place needs special handling 
  if (*l == NULL || (*l)->val > x) { 
    p = malloc(sizeof(struct node)); 
    p->val = x; 
    p->next = *l; 
    *l = p; 
  } else { 
    p = *l; 
    while (p->next != NULL && p->next->val < x) { p = p->next; }

    q = malloc(sizeof(struct node)); 
    q->val = x; 
    q->next = p->next; 
    p->next = q; 
  } 
}