c++复杂链表拷贝的方法是什么
c++复杂链表拷贝的方法是什么
这篇文章主要介绍“c++复杂链表拷贝的方法是什么”，在日常操作中，相信很多人在c++复杂链表拷贝的方法是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”c++复杂链表拷贝的方法是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
题目：请实现函数ComplexListNode* Clone(ComplextListNode* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个pNext指针指向下一个结点外，还有一个pSibling指向链表的任意结点或者NULL。
结点的C++定义如下：
template<class T>
struct ComplexListNode
{
T value;
ComplexListNode* pNext;
ComplexListNode* pSibling;
};
如图 实箭头表示pNext 虚箭头表示pSibling
（问题 主要是要解决pSibling）
方案一：1、根据pNext先复制一个A' ->B'->C'->D'->E'新链表
2、 设置新链表的每个结点的pSibling
每次都从原链表的头开始向后扫描 从对应点开始 找到pSlibing后记下次数 再在新链表根据此数找到新链表的pSlibling
比如B->E 则设置一个count从头A开始扫，找出B 和 E之间的间隔结点数3 根据这个count
设置B'的pSibling
方案一缺点：
1、每个结点pSlibling的解决都是从头找 时间复杂度为O(n^2) 有点大
方案二：（优化方案一 ，解决pSlibling时间复杂度大的问题 ）
1、 设置一个索引（哈希表） 将新表和旧表的 每个结点的地址对应起来 这样就能在O(1)的时间复杂度根据旧表的结点指针 找到新表结点指针 所以总时间复杂度为O(n)
2、 方案二多用了一张表 ，空间复杂度为O(n) 相当于 用空间换时间 将时间复杂度从O(n^2)降到O(n)
方案三:（相对最优的 优化方案二 不用辅助空间 实现时间复杂度O(n)）：
1、 先复制每个结点 不过把新结点 链接到原链表对应 结点的后面
如： A->A'->B->B'->C->C'->D->D'->E->E'
2、这个新旧一体链有一个特点 那就是 【新结点的pSlibling 是 对应旧结点的pNext】
如 A->C 则 A'->C' C'是C的pNext
3、 设置完后 奇偶节点拆链 分开新旧链表
方案三代码：
//----------ComplexListNode.hpp-----------
#pragma once
// 复杂链表的 拷贝 （复杂链表：链表中还有一个指针pSibling指向别的节点）
template<class T>
struct ComplexListNode
{
ComplexListNode()
:pNext(NULL)
,pSibling(NULL)
{}
ComplexListNode(const T& v)
:pNext(NULL)
,pSibling(NULL)
,value(v)
{}
T value;
ComplexListNode* pNext;
ComplexListNode* pSibling;// 随机指向 兄弟节点
};
/* 创建每个新节点pCloned 分别链接到对应的 原节点 pNode后面 */
template<class T>
void CloneNode(ComplexListNode<T>* pHead)
{
ComplexListNode<T>* pNode = pHead;
while(pNode != NULL)
{
ComplexListNode<T>* pCloned = new ComplexListNode<T>(pNode->value);
pCloned->pNext = pNode->pNext;
pNode->pNext = pCloned;
pNode = pCloned->pNext;
}
}
/* 设置复制出来的节点 的 pSlibling值*/
template<class T>
void ConnectSiblingNodes(ComplexListNode<T>* pHead)
{
ComplexListNode<T>* pNode = pHead;
while (pNode != NULL)
{
ComplexListNode<T>* pCloned = pNode->pNext;
if (pNode->pSibling != NULL)
{
// 因为pCloned在对应的pNode后面
// 所以pCloned的pSlibling也在 对应的pNode的pSlibling后面
// 包含pNode指向自己的情况
pCloned->pSibling = pNode->pSibling->pNext;
}
pNode = pCloned->pNext;
}
}
/* 拆分合并的链表 （从1开始）奇数位置上组成原链表 偶数位置上是复制出来的新链表*/
template<class T>
ComplexListNode<T>* ReconnectNodes(ComplexListNode<T>* pHead)
{
ComplexListNode<T>* pNode = pHead;
ComplexListNode<T>* pClonedHead = NULL;
ComplexListNode<T>* pClonedNode = NULL;
if (pNode != NULL)
{
pClonedHead = pClonedNode = pNode->pNext;
pNode->pNext = pClonedNode->pNext;
pNode = pNode->pNext;
}
while (pNode != NULL)// pNode 比 pClonedNode多走一步 ，pNode不为空 说明后面还有至少一个 pClonedNode
{
pClonedNode->pNext = pNode->pNext;
pClonedNode = pClonedNode->pNext;
pNode->pNext = pClonedNode->pNext;
pNode = pNode->pNext;
}
return pClonedHead;
}
// 复制复杂链表函数
template<class T>
ComplexListNode<T>* Clone(ComplexListNode<T>* pHead)
{
CloneNode<T>(pHead);
ConnectSiblingNodes<T>(pHead);
return ReconnectNodes<T>(pHead);
}
//---------------test.cpp --------------
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include "ComplexListNode.hpp"
using namespace std;
void testComplexListNode()
{
ComplexListNode<int> L1(1);
ComplexListNode<int> L2(2);
ComplexListNode<int> L3(3);
ComplexListNode<int> L4(4);
ComplexListNode<int> L5(5);
L1.pNext = &L2;
L2.pNext = &L3;
L3.pNext = &L4;
L4.pNext = &L5;
// 1 ->2 ->3 ->4 ->5
// pSibling
// 2->2
L2.pSibling = &L2;
// L3->L1
L3.pSibling = &L1;
// L5->L1
L5.pSibling = &L1;
ComplexListNode<int>* Head2 = Clone(&L1);
}
int main()
{
testComplexListNode();
return 0;
}
到此，关于“c++复杂链表拷贝的方法是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
