两个有序链表的合并-蒲公英云

两个有序链表的合并

对于两个有序链表的合并问题，在《剑指offer》中，采用的是如下递归的方式完成的，即：

listNode* merge(listNode* pHead1, listNode* pHead2){
    if(pHead1 == NULL)
        return pHead2;
    else if (pHead2 == NULL)
        return pHead1;
    listNode* pMergedHead = NULL;
    if(pHead1->value < pHead2->value){
        pMergedHead = pHead1;
        pMergedHead->next = merge(pHead1->next, pHead2);
    }else{
        pMergedHead = pHead2;
        pMergedHead->next = merge(pHead1, pHead2->next);
    }
    return pMergedHead;
}

但是，上面算法是不含头结点的。本人写了三种方法，都是带头结点的：

using namespace std;
struct ListNode{
    int data;
    ListNode *next;
};
ListNode* Create_Linklist(int *arr, int len)
{
    ListNode* head = new ListNode();
    head->next = NULL;
    ListNode* L = head;
    for (int i = 0; i < len; i++)
    {
        ListNode* newn = new ListNode();
        newn->data = arr[i];
        newn->next = NULL;
        L->next = newn;
        L = L->next;
    }
    return head;
}
ListNode* Merge1(ListNode* &h1, ListNode* &h2) //新建链表L3作为合并后的链表
{
    if (h1 == NULL || h1->next == NULL)return h2;
    if (h2 == NULL || h2->next == NULL)return h1;
    ListNode* L1 = h1;
    L1 = L1->next;
    ListNode* L2 = h2;
    L2 = L2->next;
    while (L1&&L2)
    {
        if (L1->data <= L2->data)L1 = L1->next;
        else
        {
            ListNode* temp = L2;
            L2 = L2->next;
            temp->next = L1;
            L1 = temp;
        }
    }
    return h1;
}
void Merge2(ListNode* &head, ListNode* h1, ListNode* h2)//链表L1作为合并后的链表
{
    if (h1 == NULL || h1->next == NULL)head = h2;
    if (h2 == NULL || h2->next == NULL)head = h1;
    ListNode* L1 = h1->next;
    ListNode* L2 = h2->next;
    head = new ListNode();
    head->next = NULL;
    ListNode* L = head;
    while (L1 && L2)
    {
        if (L1->data <= L2->data)
        {
            L->next = L1;
            L1 = L1->next;
            L = L->next;
            L->next = NULL;
        }
        else
        {
            L->next = L2;
            L2 = L2->next;
            L = L->next;
            L->next = NULL;
        }
    }
    if (!L1)
    {
        L->next = L2;
    }
    if (!L2)
    {
        L->next = L1;
    }
}
ListNode* Merge3(ListNode* head, ListNode* h1, ListNode* h2)//利用递归实现，注意本人实现的是带头结点的两个有序链表合并
{
    if (h1 == NULL)return h2;
    if (h2 == NULL)return h1;
    ListNode* L1 = h1;
    ListNode* L2 = h2;
    if (L1->data <= L2->data)
    {
        head = L1;
        head->next = Merge3(head, L1->next, L2);
    }
    else
    {
        head = L2;
        head->next = Merge3(head, L1, L2->next);
    }
    return head;
}
void Print_LinkList(ListNode* &head)
{
    if (head)
    {
        ListNode* L = head;
        L = L->next;
        while (L)
        {
            cout << L->data;
            L = L->next;
        }
    }
}
void main(int argc, char *argv[])
{
    int arr1[] = { 1, 3, 5, 7 };
    ListNode* h1 = Create_Linklist(arr1, sizeof(arr1) / sizeof(int));
    int arr2[] = { 2, 4, 6 };
    ListNode* h2 = Create_Linklist(arr2, sizeof(arr2) / sizeof(int));
    //ListNode* merge1 = Merge1(h1, h2);   //链表L1作为合并后的链表
    //ListNode* merge2 = NULL;
    //Merge2(merge2,h1,h2);   //新建链表L3作为合并后的链表
    ListNode* L1 = h1; ListNode* L2 = h2;   //利用递归实现，注意本人实现的是带头结点的两个有序链表合并，因此需要先将L1和L2后移，并用merge3->next带人Merge3函数
    L1 = L1->next; L2 = L2->next;
    ListNode* merge3 = new ListNode();
    merge3->next = NULL;
    merge3->next = Merge3(merge3->next, L1, L2);
    Print_LinkList(merge3);
}