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