Write a C program to insert nodes into a linked list in a sorted fashion? 

Discuss it!          



The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node. 

Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function. 



// Special case code for the head end 
void linkedListInsertSorted(struct node** headReference, struct node* newNode) 
{ 
  // Special case for the head end 
  if (*headReference == NULL || (*headReference)->data >= newNode->data) 
  { 
     newNode->next = *headReference; 
     *headReference = newNode; 
  } 
  else 
  { 
     // Locate the node before which the insertion is to happen! 
     struct node* current = *headReference; 
     while (current->next!=NULL && current->next->data < newNode->data) 
     { 
        current = current->next; 
     } 
     newNode->next = current->next; 
     current->next = newNode; 
   } 
}