#include <stdio.h>

#define SIZEOFARRAY(arr)  (sizeof((arr))/sizeof((arr)[0]))

struct Node
{
  struct Node *pNext;
  int data;
};

struct Node*  CreateList(int n, int  *pData);
void          PrintList(struct Node *pHead);
struct Node* MergeSort(struct Node *pList1, struct Node *pList2);

int main(int argc, char *args[])
{
    int data1[] = {10, 20, 30, 40, 50 };
    int data2[] = {20, 40, 60, 80, 100};

    struct Node *pList1 = CreateList(SIZEOFARRAY(data1), (int *) data1);
    struct Node *pList2 = CreateList(SIZEOFARRAY(data2), (int *) data2);
    
    PrintList(pList1); 
    PrintList(pList2);

    printf("\n\nMerged Lists are ...\n\n");

    PrintList(MergeSort(pList1, NULL));
    PrintList(MergeSort(NULL, pList2));
    PrintList(MergeSort(pList1, pList2));

    return 0;
}

struct Node*  CreateList(int n, int  *pData)
{
    struct Node *pHead;
    struct Node *pCurrent, *pTemp;
    int i;

    if (NULL == pData || n <= 0) return NULL;
 
    pTemp = NULL; pCurrent = NULL; pHead = NULL;

    for (i = 0; i < n; i++)
    {
        pCurrent = (struct Node *) malloc(sizeof(struct Node));
        if (NULL == pCurrent) goto cleanup;

        if (NULL == pHead) pHead = pCurrent;

        pCurrent->data = pData[i];
        pCurrent->pNext = NULL;

        if (NULL != pTemp) { pTemp->pNext = pCurrent; }
        pTemp = pCurrent;
    }

    return pHead;

cleanup:
    for(pCurrent = pHead; pCurrent != NULL; )
    {
        pTemp = pCurrent->pNext;
        free(pCurrent);
        pCurrent = pTemp; 
    }

    return NULL;
}

void PrintList(struct Node *pList)
{
    struct Node *pMover = pList;

    printf("\nList :  ");
    if (NULL == pList) printf("(EMPTY)");

    while(pMover)
    {
        printf("%d, ", pMover->data);
        pMover = pMover->pNext;
    }
}

struct Node* MergeSort(struct Node *pList1, struct Node *pList2)
{
    struct Node *pMover1 = pList1;
    struct Node *pMover2 = pList2;
    struct Node *pHead, *pTail;

    pHead = NULL; pTail = NULL;

    while (pMover1 && pMover2)
    {
        if (pMover1->data < pMover2->data)
        {
            if (NULL != pTail) pTail->pNext = pMover1;
            pTail = pMover1;
            pMover1 = pMover1->pNext;
        }
        else
        {
            if (NULL != pTail) pTail->pNext = pMover2;
            pTail = pMover2;
            pMover2 = pMover2->pNext;
        }

        pTail->pNext = NULL;
        if (NULL == pHead) pHead = pTail;
    }

    if (NULL != pMover1) 
    { 
        if (NULL != pTail) { pTail->pNext = pMover1; }
        if (NULL == pHead) pHead = pMover1;
    }

    if (NULL != pMover2) 
    { 
        if (NULL != pTail) { pTail->pNext = pMover2; }
        if (NULL == pHead) pHead = pMover2;
    }

    return pHead;
}

List :  10, 20, 30, 40, 50, 
List :  20, 40, 60, 80, 100, 

Merged Lists are ...


List :  10, 20, 30, 40, 50, 
List :  20, 40, 60, 80, 100, 
List :  10, 20, 20, 30, 40, 40, 50, 60, 80, 100,