【数据结构】单链表—合并两个排序链表 — 递归

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍使按照递增排序的。

思路：

代码如下：

template<class T>
struct ListNode
{
    T _value;
    ListNode<T>* _next;

    ListNode(const T& value)
        :_value(value),_next(NULL)
    {}
};

template<class T>
class List
{
public:
    List()
        :_head(NULL)
    {}
    bool PushBack();
    ListNode<T>* Merger(ListNode<T>* head)
    {
        return _Merger(_head,head);
    }

    ListNode<T>* _Merger(ListNode<T>* head1,ListNode<T>* head2)//合并两个有序链表，返回新链表的指针
    {
        if(head1 == NULL)
            return head2;
        if(head2 ==NULL)
            return head1;

        ListNode<T>* NewHead = NULL;
        if(head1->_value < head2->_value)//_head为新链表头节点
        {
            NewHead = head1;
            NewHead->_next = _Merger(head1->_next,head2);
        }
        else
        {
            NewHead = head2;
            NewHead->_next = _Merger(head1,head2->_next );
        }
        return NewHead;//一定要给上一层返回！
    }
private:
    ListNode<T>* _head;
};