struct node* SortedInsert(struct node* head, int newData)
{
// Special case for the head end
if ( head == NULL || head ->data >= newData)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate node
newNode->data = newData; // put in the data
newNode->next = head;
head = newNode;
}
else
{
// Locate the node before the point of insertion
struct node* current = head;
while (current->next!=NULL && current->next->data<newData)
current = current->next;
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate node
newNode->data = newData; // put in the data
newNode->next = current->next;
current->next = newNode;
}
return head;

struct node* SortedMerge(struct node* a, struct node* b)
{
struct node dummy; // a dummy first node to hang the result on
struct node* tail = &dummy; // Points to the last result node so tail->next is the place to add new nodes
to the result.
dummy.next = NULL;
while (1)
{ // if either list runs out, use the other list
if (a == NULL)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate node
newNode->data = b->data; // put in the data
newNode->next = NULL;
tail->next = newNode;
b = b->next;
}
else if (b == NULL) {
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate node
newNode->data = a->data; // put in the data
newNode->next = NULL;
tail->next = newNode;
a = a->next;
}
else
if (a->data <= b->data)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate
node
newNode->data = a->data; // put in the data
newNode->next = NULL;
tail->next = newNode;
a=a->next;
}
else
{
struct node* newNode = (struct node*) malloc(sizeof(struct node)); // allocate
node
newNode->data = b->data; // put in the data
newNode->next = NULL;
tail->next = newNode;
b=b->next;
}
tail = tail->next;
if (a == NULL && b == NULL)
break;
}
return(dummy.next);
}

void PrintList(struct node* head)
{
struct node* current = head;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
printf("\n\n");
}

#include <stdio.h>
struct node {
    int data;
    struct node *next;
};

int main()
{
    void PrintList(struct node* head);
    struct node* SortedInsert(struct node* head, int newData);

    int dataitem;

    struct node *list1 = NULL; /* Head number 1 == NULL for empty list */
    struct node *list2 = NULL; /* Head number 2 == NULL for empty list */

    /* get stuff into list number 1
     * by getting integer dataitems and repeatedly executing
     * the following:
     */
    /* some kind of loop {*/
         list1 = SortedInsert(list1, dataitem);
    /* } end of list1 stuff */

    /* get stuff into list number 2
     * by getting integer dataitems and repeatedly executing
     * the following:
     */
    /* some kind of loop {*/
        list2 = SortedInsert(list1, dataitem);
    /* } end of list2 stuff */

    printf("List number 1:\n");
    PrintList(list1);
    printf("\nList number 2:\n");
    PrintList(list2);

    /* Now call the merge/sort routine and print the results
     * printf("Merged list:\n");
     * PrintList(...
     */

    return 0;
}