soting a linked list

I got this function to write within a linked list program to insert a node into an ordered list.

Pre-condition:head is head of a linked list(NULL if the list is empty)
the last node has "next" equal to NULL
Also, the datum fields of the linked list are in ascending order
Post condition: A node is inserted with "datum" equal to the parameter n, The linked list is still in order.

Code:

---

void InsertNodeInOrderedList(nodeptr& head, int n);

---

What I have is:

Code:

---

void insertNodeInOrderedList( nodeptr& head, int n) {
        int datum1, datum2;
        nodeptr temp = new node;
        nodeptr temp2 = head;
        if(head == NULL) {
                head = temp;        //set head to new node       
                temp -> datum = n;        //data in
                temp->next = NULL;        //next node is NULL
               
               
        }
        else  //if list is empty
        {
                while(temp2->next !=NULL)
                {
                        temp2 = temp2 -> next;        //next node will be head, if the next node is not of NULL
                }
                                       
               
                temp2 -> next = temp;  //set the next node to be the new node
                temp -> datum = n;  //datum in the new node will be equal to parameter n
                datum1 = temp2->datum;  //initialize datum1 to be data of the head
                datum2 = temp2->next->datum;  //initialize datum1 to be data of the next node
                if(datum1 < datum2){  //test
                        temp2 = temp;  //head will equal new node
                        temp2->next = temp->next;  //next node will equal next new node
                       
                }
                temp ->next = NULL;
               
               
        }
}

---

I even put my explanation all over the place to help anyone in figuring what I am thinking. Oh I feel this is needed.

Code:

---

typedef struct node * nodeptr

struct node {
      int datum;
      nodeptr next;
};

---

I have played and played with this thing trying to get it to work. Well it will just put on the input, but not order it. I thought I had the understandment on this down, but I guess not so well. Could someone please give me some help?

Compare and contrast:

Code:

---

#include <iostream>

struct node {
  int data;
  node *next;

  node ( int init, node *link )
    : data ( init ), next ( link )
  {}
};

node *insert_ordered ( node *list, int data )
{
  if ( list == 0 ) {
    // Empty list
    list = new node ( data, 0 );
  }
  else if ( data < list->data ) {
    // Head insertion
    list = new node ( data, list );
  }
  else {
    // Internal insertion
    node *it = list;

    // Find the end of the list or the first larger item
    while ( it->next != 0 && data > it->next->data )
      it = it->next;

    // Insert before the first larger item
    it->next = new node ( data, it->next );
  }

  return list;
}

int main()
{
  node *list = 0;

  for ( int i = 0; i < 10; i++ )
    list = insert_ordered ( list,rand() % 100 );

  for ( node *it = list; it != NULL; it = it->next )
    std::cout<< it->data <<' ';
  std::cout<<std::endl;
}

---

Remember to consider all of your possible cases. The first and most obvious case is an empty list. Then you have three cases for ordered insertion: at the head, at the tail, somewhere inbetween. The latter two can be merged together, so the only other special case aside from an empty list is when the new item is smaller than the head.