Chapter 2: Basic Abstract Data Types. Problem 2.3.a

// a program to merge two sorted lists
//

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 


void CreateList1(NODE** list)
{
    if( !list )
        return;

    int array[] = { 1, 2, 3, 5, 6 };
    NODE* curr = NULL;  
    for( int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
    {
        NODE* newNode = new NODE;
        newNode->nValue = array[i]; 
        newNode->next = NULL;

        //insert it
        if( curr == NULL )
        {
            //first node
            curr = newNode;
            *list = curr;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = newNode;
        }
    }
}

void CreateList2(NODE** list)
{
    if( !list )
        return;

    int array[] = { 0, 1, 4, 5, 6 };
    NODE* curr = NULL;  
    for( int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
    {
        NODE* newNode = new NODE;
        newNode->nValue = array[i]; 
        newNode->next = NULL;

        //insert it
        if( curr == NULL )
        {
            //first node
            curr = newNode;
            *list = curr;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = newNode;
        }
    }
}

void PrintList( NODE* list)
{
    if( !list )
        return;

    cout << "List is --> " << endl;
    for( NODE* curr = list; curr != NULL; curr = curr->next )
        cout << "[" << curr->nValue << "]" << endl;
    cout << "<-- End of list." << endl;
}

NODE* MergeTwoLists( NODE* list1, NODE* list2 )
{
    if( !list1 || !list2 )
        return NULL;

    NODE* newList = NULL; 
    NODE* currNode = NULL; 
    NODE* nodeToTake = NULL;  

    while( list1 && list2 )
    {
        if( list1->nValue <= list2->nValue )
        {
            //We take this node.
            nodeToTake = list1; 
            list1 = list1->next;
        }
        else
        {
            nodeToTake = list2;
            list2 = list2->next; 
        }

        if( newList == NULL )
        {
            newList = nodeToTake;
            currNode = nodeToTake;
        }
        else
        {
            currNode->next = nodeToTake;
            currNode = currNode->next;
        }
    }

    if( list1 )
    {
        //append list 1 to the new list
        currNode->next = list1; 
    }
    else
    {
        //append list 2 to the new list
        currNode->next = list2;
    }
    return newList; 
}

void main()
{
    NODE* list1 = NULL; 
    NODE* list2 = NULL;    
    CreateList1(&list1);
    CreateList2(&list2);
    PrintList(list1);
    PrintList(list2);
    NODE* mergeList = MergeTwoLists(list1, list2); 
    PrintList(mergeList);
}