学步园

两个链表，已经有序排列，现在将其合并并输出新的链表

#include <iostream>
using namespace std;
#include <vector>
using std::vector;

#include <stdlib.h>
#ifndef _WIN32
#include <unistd.h>
#else
#include <time.h>
#endif

template<typename T>
struct Node
{
public:
    Node(T value)
    {
        mValue = value;
        mNextNode = 0;
    }

    T getValue() {return mValue;}
    void setNextNode( Node<T> *next)
    {
        mNextNode = next;
    }
    Node<T> *getNextNode() {return mNextNode;}
private:
    Node<T> *mNextNode;
    T mValue;
};

template<typename T>
Node<T>*
    buildList ( vector<T> & list )
{
    Node<T> * head = NULL;
    Node<T> * currentNode  = head;
    for ( int i = 0 ; i < list.size(); i ++ )
    {
        Node<T> *tmp = new Node<T>(list[i]);
        if ( 0 == currentNode )
        {
            currentNode = tmp;
            head = currentNode;
        }
        else
        {
            currentNode ->setNextNode(tmp);
            currentNode = tmp;
        }
    }
    return head;
}

template<typename T>
void dump(Node<T> *head)
{
    while( head )
    {
        cout << head->getValue()<<" ";
        head = head->getNextNode();
    }
    cout << endl;
}

template<typename T>
Node<T> * mergeList( Node<T> *input1,Node<T> *input2 )
{
    Node<T> *retval = 0;
    if ( !input1 && !input2 )
    {
        return retval;
    }
    if ( !input1 )
    {
        return input2;
    }
    if ( !input2 )
    {
        return input1;
    }
    if ( input1->getValue() < input2->getValue() )
    {
        retval = input1;
        Node<T> *nextNode = mergeList<T>(input1->getNextNode(),input2);
        retval->setNextNode(nextNode);
    }
    else
    {
        retval = input2;
        retval->setNextNode(mergeList(input1,input2->getNextNode()));
    }
    return retval;
}

template<typename T>
Node<T> * noneRecursiveMerge( Node<T> * list1,Node<T> *list2 )
{
    Node<T> * retval = NULL;
    if ( !list1 && ! !list2 )
    {
        return retval;
    }
    if ( !list1 )
    {
        return list2;
    }
    if ( !list2 )
    {
        return list1;
    }
    Node<T> * currentNode = retval;
    while ( list1 && list2 )
    {
        if ( list1->getValue() < list2->getValue() )
        {
            if ( !currentNode )
            {
                currentNode = list1;
                retval = currentNode;
            }
            else
            {
               currentNode->setNextNode(list1);
               currentNode = list1;
            }
            list1 = list1->getNextNode();
        }
        else
        {
            if ( !currentNode )
            {
                currentNode = list2;
                retval = currentNode;
            }
            else
            {
                currentNode->setNextNode(list2);
                currentNode = list2;
            }
            list2 = list2->getNextNode();
        }
    }
    if ( list1 )
    {
        currentNode->setNextNode(list1);
    }
    if ( list2 )
    {
        currentNode->setNextNode(list2);
    }
    return retval;
}

void testRecursive()
{
    vector<int> v1;
    vector<int> v2;
    srand(time(NULL));
    for ( int i = 0 ; i < 20; i ++ )
    {
        int value = rand()%20;
        if ( value % 2 == 0 )
        {
            v2.push_back(i);
        }
        else
        {
            v1.push_back(i);
        }
    }
    Node<int> *list1 = buildList<int>(v1);
    Node<int> *list2 = buildList<int>(v2);
    dump(list1);
    dump(list2);
    Node<int> *result = mergeList<int>(list1,list2);
    dump(result);
}

void testNoneRecursive()
{
    vector<int> v1;
    vector<int> v2;
    srand(time(NULL));
    for ( int i = 1; i <= 20; i ++ )
    {
        int value = rand()%100;
        if ( value % 2 )
        {
            v2.push_back(i);
        }
        else
        {
            v1.push_back(i);
        }
    }
    Node<int> *list1 = buildList<int>(v1);
    Node<int> *list2 = buildList<int>(v2);
    dump(list1);
    dump(list2);
    Node<int> *result = noneRecursiveMerge(list1,list2);
    dump(result);
}

int main()
{
    testRecursive();
    cout << "test 2"<<endl;
    testNoneRecursive();
    return 0;
}