迭代合并
思想:从表头到表尾,依次比较,有小到大排序
步骤:
第一步:首先判断两个链表,如果存在两个链表中有一个为空链表,则输出另外一个链表。
第二步:定义两个节点,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; }