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

//program to merge n sorted lists
//in this program, n = 10. 

#include <iostream>
using namespace std;

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

void CreateLists(NODE** lists, int nLists); 
NODE* CreateSortedList(int nStart, int nInc, int nTotal); 
void PrintLists( NODE** list, int nLists); 
void PrintList( NODE* list); 
NODE* MergeAllSortedLists(NODE** lists, int nLists); 
bool MoreThanOneListRemaining(NODE** lists, int nLists); 

void main()
{
    //array of sorted lists
    NODE* lists[10] = { 0 }; //Note: In C, there is no easy way to initialize all elements (not considering memset) - except if you want to initialize
                             //all elements to 0 - which is what I want in this case. 
                             
    CreateLists(lists,sizeof(lists)/sizeof(lists[0])); 
    PrintLists(lists,sizeof(lists)/sizeof(lists[0])); 
    NODE* newList = MergeAllSortedLists(lists, sizeof(lists)/sizeof(lists[0]));
    PrintList(newList); 
}

void CreateLists(NODE** lists, int nLists) //Pass array by reference
{
    if( !lists )
        return;

    int nStart = 0; 
    int nInc = 2; 
    for( int n = 0; n < nLists; n++ )
    {
        lists[n] = CreateSortedList(nStart,nInc,10); 
        //Just to add some variety to the lists created
        nStart += 10; 
        if( nInc == 2 )
            nInc = 1; 
        else 
            nInc = 2; 
    }
}

//Creates a sorted list of nTotal elements. 
//First element assigned a value nStart. 
//Second element = nStart+nInc
//and so on...
NODE* CreateSortedList(int nStart, int nInc, int nTotal)
{
    NODE* head = NULL;
    NODE* curr = NULL;
    for( int i = 0; i < nTotal; i++ )
    {
        NODE* newNode = new NODE; 
        newNode->nValue = nStart; 
        newNode->next = NULL;
        if( !head )
        {
            //first node
            head = newNode;
            curr = head;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = curr->next;
        }
        nStart += nInc; 
    }
    return head;
}
        
void PrintLists( NODE** list, int nLists)
{
    for( int n = 0; n < nLists; n++ )
    {
        PrintList(list[n]);
    }
}

void PrintList( NODE* list)
{
    if( !list )
    {
        cout << "Empty list." << endl;
        return;
    }
    cout << "List is --> " << endl;
    for( NODE* curr = list; curr != NULL; curr = curr->next )
        cout << curr->nValue << " "; 
    cout << endl << "<-- End of list." << endl;
}

//the main function that does the sorting
NODE* MergeAllSortedLists(NODE** lists, int nLists)
{
    if( !lists )
        return NULL; 

    NODE* newList = NULL;
    NODE* nodeToTake = NULL; 
    NODE* currNode = NULL;
    int nListToInc = 0; //This points to the list from a node is taken

    //Continue until we have just one list left
    while( MoreThanOneListRemaining(lists,nLists) )
    {
        nListToInc = -1; 
        for( int n = 0; n < nLists; n++ )
        {
            //find the node that we want to append to our new list
            if( lists[n] )
            {
                if( nodeToTake )
                {
                    if( nodeToTake->nValue > (lists[n])->nValue )
                    {
                        nodeToTake = lists[n]; 
                        nListToInc = n; 
                    }
                }
                else
                {
                    nodeToTake = lists[n]; 
                    nListToInc = n; 
                }
            }
        }
        if( nListToInc == -1 )
        {
            cout << "Error in logic." << endl;
            return NULL;
        }
        else
        {
            lists[nListToInc] = (lists[nListToInc])->next; 
        }
        //we have our node that we want to append to the new list
        if( !newList )
        {
            newList = nodeToTake;
            currNode = newList;
        }
        else
        {
            currNode->next = nodeToTake;
            currNode = currNode->next;
        }
        nodeToTake = NULL;
    }

    //At this point, we'll have one list left
    NODE* lastList = NULL;
    for( int n = 0; n < nLists; n++ )
    {
        if( lists[n] )
        {
            lastList = lists[n]; 
            break;
        }
    }
    if( lastList )
        currNode->next = lastList;

    return newList;
}

//returns true if valid elements in array > 1.
//return false if valid elements in array <= 1. 
bool MoreThanOneListRemaining(NODE** lists, int nLists)
{
    if( !lists )
        return false;
    int nCount = 0;
    for( int n = 0; n < nLists; n++ )
    {
        if( lists[n] )
            nCount++;
    }
    return (nCount > 1 ? true : false);
}