合并两个排好序的单链表

#include <iostream>
using namespace std;

typedef struct ListNode
{
    int value;
    ListNode* next;
}ListNode;

void createList_1(ListNode *&head)
{
    head = new(ListNode);
    head->value = 1;
    head->next = NULL;

    ListNode *p2 = new(ListNode);
    p2->value = 3;
    p2->next = NULL;
    head->next = p2;

    ListNode *p3 = new(ListNode);
    p3->value = 5;
    p3->next = NULL;
    p2->next = p3;

    ListNode *p4 = new(ListNode);
    p4->value = 7;
    p4->next = NULL;
    p3->next = p4;
}
void createList_2(ListNode *&head)
{
    head = new(ListNode);
    head->value = 2;
    head->next = NULL;

    ListNode *p2 = new(ListNode);
    p2->value = 4;
    p2->next = NULL;
    head->next = p2;

    ListNode *p3 = new(ListNode);
    p3->value = 6;
    p3->next = NULL;
    p2->next = p3;

}
void deleteList(ListNode *p)
{
    ListNode *next = NULL;
    while(p != NULL)
    {
        next = p->next;
        delete p;
        p = NULL;
        p = next;
    }
}



void printList(ListNode *p)
{
    while(p)
    {
        cout << p->value << "\t";
        p = p->next;
    }
    cout << endl;
}
ListNode* combinList(ListNode *head_1, ListNode *head_2)
{
    ListNode *head_3 = NULL;
    if(head_1 == NULL)
    {
        head_3 = head_2;
    }
    else if(head_2 == NULL)
    {
        head_3 = head_2;
    }
    else
    {
        ListNode *p1 = head_1;
        ListNode *p2 = head_2;
        ListNode *pre = NULL;
        if(p1->value < p2->value)
        {
            head_3 = p1;
            pre = head_3;
            p1 = p1->next;
        }
        else
        {
            head_3 = p2;
            pre = head_3;
            p2 = p2->next;
        }
        while(p1 && p2)
        {
            if(p1->value < p2->value)
            {
                pre->next = p1;
                pre = p1;
                p1 = p1->next;
            }
            else
            {
                pre->next = p2;
                pre = p2;
                p2 = p2->next;
            }
        }
        if(p1)
            pre->next = p1;
        if(p2)
            pre->next = p2;
    }
    return head_3;
}

ListNode* combinListRecursion(ListNode *head_1, ListNode *head_2)
{
    if(head_1 == NULL)
        return head_2;
    else if(head_2 == NULL)
        return head_1;
    ListNode *head = NULL;
    if(head_1->value < head_2->value)
    {
        head = head_1;
        head->next = combinListRecursion(head_1->next, head_2);
    }
    else
    {
        head = head_2;
        head->next = combinListRecursion(head_1, head_2->next);
    }
    return head;
}


int main()
{
    ListNode *head_1 = NULL;
    ListNode *head_2 = NULL;
    ListNode *head_3 = NULL;
    createList_1(head_1);
    createList_2(head_2);
    head_3 = combinListRecursion(head_1, head_2);
    printList(head_3);

    deleteList(head_1);
    deleteList(head_2);
}