//---------------------------------------------------------------------
// File: merge.cpp
// Name: Chip Dixon, modified by Sharon M. Tuttle
// last modified: 3-24-05
//
// Contract: merge: node* node* -> node*
//
// Purpose: merge the two sorted lists pointed to by <listPtr1>
//    and <listPtr2> into a single linked list, and return a
//    pointer to the first node in the sorted result.
//
// preconditions:
//    *   listPtr1 != NULL
//    *   listPtr2 != NULL
//    *   listPtr1 is a pointer to a list of nodes whose
//        data fields are sorted in ascending order
//    *   listPtr2 is a pointer to a list of nodes whose
//        data fields are sorted in ascending order
//
// postconditions:
//    *   the pointer returned points to the node whose data
//        field contains the smallest value
//    *   the pointer returned points to a list sorted in
//        ascending order that contains all of the nodes in
//        the lists originally pointed to by listPtr1 and listPtr2
//    *   listPtr1 and listPtr2 are unchanged, BUT one of them
//        points somewhere within the resulting list
//
// Examples:
//    If l1 points to a linked list of nodes with data:
//       2 3 6
//    ...and l2 points to a linked list of nodes with data:
//       1 5 9
//    then:
//       merge(l1, l2) would return a pointer to a linked list
//          containing:   1  2  3  5  6  9
//
//    Boundary: each points to a single element list
//    If l1 points to a linked list of nodes with data:
//       2
//    ...and l2 points to a linked list of nodes with data:
//       3
//    then:
//       merge(l1, l2) would return a pointer to a linked list
//          containing:   2 3
//
// libraries/other functions used: node.h
//---------------------------------------------------------------------

#include <cassert>
#include "node.h"
using namespace std;

node* merge(node* listPtr1, node* listPtr2)
{
    node *temp, *newHead;
    node *restOf1, *restOf2;

    assert(listPtr1 != NULL);
    assert(listPtr2 != NULL);

    // these pointers will walk through the 2 lists
    //     passed to merge, pointing to the next element
    //     to be considered
    //
    restOf1 = listPtr1;
    restOf2 = listPtr2;
 
    // determine which list's head pointer goes first
    if (restOf1->get_data() <= restOf2->get_data())
    {
        temp = restOf1;
        restOf1 = restOf1->get_next();
    }

    else
    {
        temp = restOf2;
        restOf2 = restOf2->get_next();
    }

    newHead = temp;

    // while we still have 2 lists of unmerged contents,
    //    merge their contents 
    //    (add appropriate next node to sorted part)
    while ((restOf1 != NULL) && (restOf2 != NULL))
    {
        // add next node of restOf1 to sorted part
        if (restOf1->get_data() <= restOf2->get_data())
        {
            temp->set_next(restOf1);
            temp = restOf1;
            restOf1 = restOf1->get_next();
        }

        // else, add next node of restOf2 to sorted part
        else
        {
            temp->set_next(restOf2);
            temp = restOf2;
            restOf2 = restOf2->get_next();
        }
    }

    // one list has now ended, to reach this point ---
    //    attach what's left of the other!
    if (restOf1 == NULL)
    {
        temp->set_next(restOf2);
    }
    else
    {
        temp->set_next(restOf1);
    }

    // now, return the newHead pointer, that now points to
    //    the beginning of the now-sorted result
    return newHead;
}