复杂链表复制——时间复杂度为O(N)

        今天我们来分享一下关于复杂链表复制，时间复杂度为O(N)的算法。

    复杂链表是拥有节点值，后继节点及随机前序节点的链表，复杂链表复制的难度在于如何找到那个随机的前序节点，一般的算法在找前序节点的效率是非常低的，需要结合被复制的链表去遍历查找，时间复杂度一般为O(N)。

   下面我们来举例说明这个时间复杂度为O(N)的复杂链表复制算法，一般用面向过程书写比较方便。

      首先，将要被复制的复杂链表如下：

 

     步骤一：在被复制的链表中对应插入拥有相应值的新节点

 

    步骤二：通过找到被复制链表的前序随机节点，找到新增节点的前序随机节点

 

    步骤三：拆掉新增结点和被复制节点间的联系，依次连接接新增加节点，并恢复被复制节点之间的连接

 

    即可得到复制后的复杂链表。

 

 

    虽然不是很喜欢在博客中粘贴代码，但还是粘贴一下我的代码吧！仅供参考！个人觉得面向过程写的比较好。

面向过程：

Complex.h
//复杂链表Y(面向过程)
#pragma once

typedef int Type;
//定一结构体
struct Clist
{
Type _data;
Clist* _next;
Clist* _random;
Clist(Type data)
:_data(data)
,_next(NULL)
,_random(NULL)
{
}
};

Clist* ComplexCP(Clist*l)
{
if(l ==NULL)return NULL;
//插入连接上
Clist* cur = l;
while(cur)
{
Clist* next = cur->_next;
Clist* add = new Clist(cur->_data);
cur->_next = add;
add->_next = next;

cur = next;
}
//找到随机链接的结点
cur =l;
while(cur)
{
Clist* next = cur->_next;
Clist* prev = cur->_random;

if(prev != NULL)
{
Clist* Pnext = prev->_next;
next->_random = Pnext;
}
else
next->_random = NULL;

cur = next->_next;
}
//取出新链
cur = l;
Clist* newlist = NULL;
Clist* tail = NULL;
while(cur)
{
Clist* newPoint = cur->_next;
Clist* next = newPoint->_next;

cur->_next = next;
if(newlist == NULL)
{
newlist = newPoint;
tail = newPoint;
}
else
{
tail->_next = newPoint;
tail = tail->_next;
}

cur = next;
}
return newlist;
}

void Printf(Clist*l)
{
Clist* cur = l;
while(cur)
{
cout<<"结点 "<<cur<<" : "<<cur->_data<<" , next-> ";
if(cur->_next != NULL)
cout<<cur->_next->_data<<" , random-> ";
else
    cout<<"NULL , random-> ";

if(cur->_random != NULL)
   cout<<cur->_random->_data<<endl;
else
   cout<<" NULL "<<endl;

cur = cur->_next;
}
}

void TestCLCP()//复杂链表的复制面向过程
{
Clist* node1 = new Clist(5);
Clist* node2 = new Clist(4);
Clist* node3 = new Clist(3);
Clist* node4 = new Clist(2);
Clist* node5 = new Clist(1);

node1->_next = node2;
node2->_next = node3;
node3->_next = node4;
node4->_next = node5;
node5->_next = NULL;

node1->_random = node4;
node2->_random = NULL;
node3->_random = node5;
node4->_random = node2;
node5->_random = node1;

cout<<"打印node1: "<<endl;
Printf(node1);

Clist* CPlist = ComplexCP(node1);
cout<<endl<<"CPlist= ComplexCP(node1):>"<<endl<<"打印CPlist: "<<endl;
Printf(CPlist);
}
Run.h
#include<iostream>
#include<string>//不加.h
using namespace std;
#include"Complex.h"//复杂链表Y(面向过程)

int main()
{
cout<<"*******************************"<<endl;
cout<<"复杂链表的复制(面向过程)："<<endl<<endl;
TestCLCP();//复杂链表的复制面向过程
cout<<"*******************************"<<endl;
system("pause");
return 0;
}

面向对象（low）

//复杂链表的复制
#pragma once

template<class T>
class CListNode
{
public:
T _data;
CListNode<T>* _prev;
CListNode<T>* _next;
CListNode()
{}
CListNode(T data)
:_data(data)
,_prev(NULL)
,_next(NULL)
{
}
};

template<class T>
class CList
{
public:
typedef CListNode<T> Node;
//构造,拷贝构造(*),find,Insert,析构
CList()
:_head(NULL)
{
}
CList(CList<T>& l)
:_head(NULL)
{
Node* Lhead = l._head;
if(Lhead != NULL)
{
Node* prev = NULL;
Node* cur = Lhead;
while(cur)//链上
{
Node* next = cur->_next;
Node* add = new Node(cur->_data);

cur->_next = add;
add->_next = next;

prev = add;
cur = next;
}
//add加上prev
cur = Lhead;
while(cur)
{
Node* prev = cur->_prev ;
Node* next = cur->_next;

if(prev != NULL)
{
Node* Pnext = prev->_next;
next->_prev = Pnext;
}
else
next->_prev = NULL;

cur = next->_next;
}
//拆链
cur = Lhead;
Node* next = cur->_next;
_head = next;
while(next->_next)
{
Node* Cnext = next->_next;//你有一万个见他的理由，却没有了一个见面的身份
Node* Nnext = Cnext->_next;

cur->_next = Cnext;
cur = next->_next;
next->_next = Nnext;
next = cur->_next;
}
cur->_next = next->_next;
}
}
CList*  operator=(CList<T> l)
{
swap(l._head, _head);
return this;
}

~CList()
{
_Clear(_head);
_head = NULL;
}

bool PushBack(T data)
{
return _PushBack(_head, data);
}
Node* Find(const T& data)
{
return _Find(_head, data);
}
void Print()
{
//cout<<"打印链表： ";
_Print(_head);
cout<<endl;
}
protected:
void _Clear(Node*  cur)
{
if(cur == NULL) return;
Node* pt = cur->_next;
delete cur;
_Clear(pt);
}
void _Print(Node* cur)
{
if(cur == NULL) return;

cout<<"节点 0x"<<cur<<" : "<<cur->_data<<" 前序节点->"<<cur->_prev->_data <<" , 后继节点： ";
if(cur->_next == NULL)
cout<<"无";
else
cout<<cur->_next->_data<<endl;
_Print(cur->_next);
}
bool _PushBack(Node* & cur, T& data)
{
if(cur == NULL)
{
cur=new Node(data);
return true;
}
else
{
return _PushBack(cur->_next, data);
}

}
Node* _Find(Node*& cur,const T& data)
{
if(cur == NULL) return NULL;

if(cur->_data == data) return cur;
else
return _Find(cur->_next, data);
}
protected:
Node* _head;
};

void CLCP()//复杂链表的复制
{
CList<int> LS;
LS.PushBack(5);
LS.PushBack(2);
LS.PushBack(1);
LS.PushBack(4);
LS.PushBack(3);

for(int i=1; i<6; i++)
{
CListNode<int>* cur = LS.Find(i);
CListNode<int>* prev = LS.Find((2+i)%5);
if(prev == NULL)
prev = LS.Find(1);
cur->_prev = prev;

}

cout<<"LS链表打印： "<<endl;
LS.Print();
cout<<endl;

CList<int> LSCP(LS);
cout<<"LSCP链表打印： "<<endl;
LSCP.Print();

CList<int> LSCP2;
LSCP2 = LS;
cout<<"LSCP2链表打印： "<<endl;
LSCP2.Print();
}
Run.c
#include<iostream>
#include<string>
using namespace std;
#include"BST.h"
#include"VK.h"
#include"ComplexCP.h"

int main()
{
cout<<"*******************************"<<endl;
cout<<"复杂链表的复制："<<endl<<endl;
CLCP();//复杂链表的复制
cout<<"*******************************"<<endl;
system("pause");
return 0;
}

运行界面

今天的分享到此为止，望共同进步！