• 迭代合并

    思想:从表头到表尾,依次比较,有小到大排序

    步骤:

    第一步:首先判断两个链表,如果存在两个链表中有一个为空链表,则输出另外一个链表。

    第二步:定义两个节点,P1和P2,其中P1负责保存最后的链表输出数据,P2负责移动位置。

    第三步:一直比较两个链表的头节点的值,当遍历到其中一个链表的尾端时,

    再把另一个链表接上去。

  • 递归合并

    思想:若链表1 小于链表2,则合成链表指向链表1;若链表1大于等于链表2,则合成链表指向链表2

    步骤:

    第一步:首先判断两个链表,如果存在两个链表中有一个为空链表,则输出另外一个链表。

    第二步:如果表1小于表2,则表1的节点插入合并节点且表1的下一个进行递归;反之。

    第三步:输出合并节点

  • mergeLists.h
#include <iostream>
#include <vector>

struct ListNode {
    int data;
    struct ListNode *next;
    ListNode (int x) : data(x), next(nullptr) {}
};

class BaseCreateListClass {
public:
    virtual ~BaseCreateListClass() = default;
    void ShowList(ListNode *pHead);
    virtual ListNode *CreateList(std::vector<int> vec, int flag) = 0;
};

class CreateListClass : public BaseCreateListClass{
public:
    ~CreateListClass() = default;
    void ShowList(ListNode *pHead);
    ListNode *CreateList(std::vector<int> vec, int flag) override;
};

class BaseMergeListClass {
public:
    virtual ~BaseMergeListClass() = default;
    virtual ListNode *MergeLists(ListNode * pHead1, ListNode *pHead2) = 0;
};

/*迭代合并*/
class RecursiveMergeListsClass : public BaseMergeListClass {
public:
    ~RecursiveMergeListsClass() = default;
    ListNode *MergeLists(ListNode * pHead1, ListNode *pHead2);
};

/*递归合并*/
class IntertorMergeListsClass : public BaseMergeListClass {
public:
    ~IntertorMergeListsClass() = default;
    ListNode *MergeLists(ListNode * pHead1, ListNode *pHead2);
};

template <typename TempClass>
class TempMergeListClass {
public:
    virtual ~TempMergeListClass() = default;
    ListNode *MergeLists(ListNode * pHead1, ListNode *pHead2) {
        return tempClass.MergeLists(pHead1, pHead2);
    }
private:
    TempClass tempClass;
};
  • mergeLists.cpp
#include "mergeLists.h"
#include <memory>

constexpr int HEAD_INSERT = 1;
constexpr int END_INSERT = 2;

void CreateListClass::ShowList(ListNode *pHead)
{
    if (pHead == nullptr) {
        return;
    }

    while(pHead != nullptr) {
        std::cout<<" "<<pHead->data;
        pHead = pHead->next;
    }
    std::cout<<std::endl;
}

ListNode *CreateListClass::CreateList(std::vector<int> vec, int flag)
{
    if (vec.size() == 0) {
        return nullptr;
    }

    if (flag == 1) {  //头插法,反向输出
        ListNode * pHead = nullptr;
        for(auto iter = vec.begin(); iter != vec.end(); ++iter) {
            ListNode * tempNode = new ListNode(*iter);
            tempNode->next = pHead; //头插法,反向输出
            pHead = tempNode; //向前移位
        }
        return pHead;
    }else if (flag == 2) {
        ListNode *pNewNode = new ListNode(0);
        ListNode * pHead = pNewNode;
        for(auto iter = vec.begin(); iter != vec.end(); ++iter) {
            ListNode * tempNode = new ListNode(*iter);
            pHead->next = tempNode; // 尾插法, 顺序输出
            pHead = pHead->next;
        }
        return pNewNode->next;
    } else {
        return nullptr;
    }

    return nullptr;

}


/*
* 迭代合并
* 思想:从表头到表尾,依次比较,有小到大排序
* 步骤:
* 第一步:首先判断两个链表,如果存在两个链表中有一个为空链表,则输出另外一个链表。
* 第二步:定义两个节点,P1和P2,其中P1负责保存最后的链表输出数据,P2负责移动位置。
* 第三步:一直比较两个链表的头节点的值,当遍历到其中一个链表的尾端时,
*        再把另一个链表接上去。
*/
ListNode *RecursiveMergeListsClass::MergeLists(ListNode * pHead1, ListNode *pHead2)
{
    if (pHead1 == nullptr && pHead2 == nullptr) {
        return nullptr;
    }

    if (pHead1 == nullptr) {
        return pHead2;
    }

    if (pHead2 == nullptr) {
        return pHead1;
    }

    ListNode *pNewNode = new ListNode(0);
    ListNode *MergeListsNode = pNewNode;
    while (pHead1 != nullptr && pHead2 != nullptr) {
        // 头插法
        /*
        if (pHead1->data < pHead2->data) {
            pHead1->next = MergeListsNode;
            MergeListsNode = pHead1;
            pHead1 = pHead1->next;
        } else {
            pHead2->next = MergeListsNode;
            MergeListsNode = pHead2;
            pHead2 = pHead2->next;
        }
        */
        //尾插法
        if (pHead1->data < pHead2->data) {
            MergeListsNode->next = pHead1;
            MergeListsNode = MergeListsNode->next;
            pHead1 = pHead1->next;
        } else {
            MergeListsNode->next = pHead2;
            MergeListsNode = MergeListsNode->next;
            pHead2 = pHead2->next;
        }
    }

    if (pHead1 == nullptr) {
        MergeListsNode->next = pHead2;
    }

    if (pHead2 == nullptr) {
         MergeListsNode->next = pHead1;
    }
    return pNewNode->next;
}


/*
* 递归合并
* 思想:若链表1 小于链表2,则合成链表指向链表1;若链表1大于等于链表2,则合成链表指向链表2
* 步骤:
*/
ListNode *IntertorMergeListsClass::MergeLists(ListNode * pHead1, ListNode *pHead2)
{
    if (pHead1 == nullptr && pHead2 == nullptr) {
        return nullptr;
    }

    if (pHead1 == nullptr) {
        return pHead2;
    }

    if (pHead2 == nullptr) {
        return pHead1;
    }

    ListNode *MergeListsNode = nullptr;
    if (pHead1->data  < pHead2->data) {
        MergeListsNode = pHead1; //尾插入
        this->MergeLists(pHead1->next, pHead2);

    } else {
        MergeListsNode = pHead2; //尾插入
        this->MergeLists(pHead1, pHead2->next);
    }
    return MergeListsNode;
}

int main() 
{

    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8};
    CreateListClass createListClass;
    // make_unique -- c++14
    std::unique_ptr<BaseCreateListClass> baseCreateListClass = std::make_unique<CreateListClass>();
    //std::unique_ptr<BaseCreateListClass> baseCreateListClass = new CreateListClass();
    ListNode *pHeadNode1 = baseCreateListClass->CreateList(vec1, END_INSERT);
    if (pHeadNode1 == nullptr) {
        std::cout<<"the pHeadNode1 is null"<<std::endl;
    } else {
        std::cout<<"the pHeadNode1 of %d: "<<END_INSERT<<std::endl;
        createListClass.ShowList(pHeadNode1);
    }

    ListNode *pHeadNode2 = baseCreateListClass->CreateList(vec2, END_INSERT);
    if (pHeadNode2 == nullptr) {
        std::cout<<"the pHeadNode2 is null"<<std::endl;
    } else {
        std::cout<<"the pHeadNode2: "<<std::endl;
        createListClass.ShowList(pHeadNode2);
    }

    TempMergeListClass<RecursiveMergeListsClass>  recursiveMergeListsClass;
    ListNode *recursiveMergeNode = recursiveMergeListsClass.MergeLists(pHeadNode1, pHeadNode2);
    if (recursiveMergeNode == nullptr) {
        std::cout<<"the recursiveMergeNode is null"<<std::endl;
    } else {
        std::cout<<"the recursiveMergeNode: "<<std::endl;
        createListClass.ShowList(recursiveMergeNode);
    }

    TempMergeListClass<IntertorMergeListsClass>  intertorMergeListsClass;
    ListNode *intertorMergeNode = intertorMergeListsClass.MergeLists(pHeadNode1, pHeadNode2);
    if (intertorMergeNode == nullptr) {
        std::cout<<"the intertorMergeNode is null"<<std::endl;
    } else {
        std::cout<<"the intertorMergeNode: "<<std::endl;
        createListClass.ShowList(intertorMergeNode);
    }

    return 1;
}