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?