Insert nodes into a linked list in a sorted fashion

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.

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


  • Time O(N)


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation