Chapter 2: Basic Abstract Data Types. Problem 2.4

//program to concatenate list of lists into a single list 
//in this program, number of lists are 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* ConcatLists(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 = ConcatLists(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 concatenation 
NODE* ConcatLists(NODE** lists, int nLists)
{
    if( !lists )
        return NULL; 

    NODE* newList = NULL; 
    NODE* currList = NULL;
    NODE* endOfNewList = NULL;

    //Run the loop for all but the last list cause it just needs to be appended
    for( int n = 0; n < nLists-1; n++ )
    {
        currList = lists[n]; 
        if( !newList )
            newList = currList;
        else
            endOfNewList->next = currList;
        //Find the end of this list for next iteration
        for( endOfNewList = currList; endOfNewList->next != NULL; endOfNewList = endOfNewList->next ); 
    }
    endOfNewList->next = lists[nLists-1]; 
    return newList; 
}