合并两个有序链表

算法（algorithm）

归并排序的最后一个步骤， 将两个有序的链表合并成一个有序链表。从每个链表中取出一个元素然后比较，之后插入新的合并链表，依次递归。

#include <iostream>

typedef struct Node {
    int v;
    Node *next;
}Node;

Node* createNode(int v){
    Node* node = new Node();
    node->v = v;
    node->next = nullptr;
    return node;
}

void addNode(Node** pRoot, int v){
    Node* pHeader = nullptr;
    if (!(pHeader = *pRoot))
    {
        pHeader = *pRoot = createNode(v);
        return;
    }

    while (pHeader->next != nullptr)
    {
        pHeader = pHeader->next;
    }
    pHeader->next = createNode(v);
}

void printList(Node** pRoot) {
    Node* pHeader = *pRoot;
    while (pHeader != nullptr)
    {
        std::cout << pHeader->v;
        pHeader = pHeader->next;
        if (pHeader != nullptr){
            std::cout << "->";
        }
    }
    std::cout << "\n@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << std::endl;
}

Node* mergeList(Node *pNode1, Node* pNode2) {
    if (pNode1 == nullptr)
    {
        return pNode2;
    }
    else if (pNode2 == nullptr)
    {
        return pNode1;
    }

    Node* pMergeList = nullptr;
    if (pNode1->v < pNode2->v)
    {
        pMergeList = pNode1;
        pMergeList->next = mergeList(pNode1->next, pNode2);
    }
    else
    {
        pMergeList = pNode2;
        pMergeList->next = mergeList(pNode1, pNode2->next);
    }
    return pMergeList;
    //非递归实现
    /*
     ListNode new_node(0);
      ListNode* ptr= &new_node;
        
        while(l1 && l2){
            if(l1->val < l2->val){
                ptr->next=l1;
                l1=l1->next;
            }else{
                ptr->next=l2;
                l2=l2->next;
            }
            ptr=ptr->next;
        }
        
        if(l1){
            ptr->next=l1;
        }
        if(l2){
            ptr->next=l2;
        }
        return new_node.next;
   */

}

void destroyList(Node** pRoot){
    Node* pHeader = *pRoot;
    while(pHeader != nullptr)
    {
        Node* pTemp = pHeader;
        pHeader = pHeader->next;
        std::cout << "delete " << pTemp->v << std::endl;
        delete pTemp;
    }
}

int main()
{
    Node* pNode1 = nullptr;
    addNode(&pNode1, 3);
    addNode(&pNode1, 5);
    addNode(&pNode1, 6);
    addNode(&pNode1, 9);
    addNode(&pNode1, 12);
    addNode(&pNode1, 15);
    printList(&pNode1);

    Node* pNode2 = nullptr;
    addNode(&pNode2, 1);
    addNode(&pNode2, 5);
    addNode(&pNode2, 8);
    addNode(&pNode2, 10);
    addNode(&pNode2, 11);
    printList(&pNode2);

    Node* mergeNode = mergeList(pNode1, pNode2);
    printList(&mergeNode);
    destroyList(&mergeNode);

    getchar();
    return 0;
}