#include<iostream>
#include<utility>
using namespace std;
struct Node
{
	int value;
	Node* next;
	Node* any;//指向某个结点
	Node(int v):value(v),any(NULL),next(NULL){}
};
/*创建一个链表，1->2->3->4->5->6->7*/
Node* CreateList()//创建一个单链表
{
   Node *head;
   Node *n1=new Node(1);
   Node *n2=new Node(2);
   Node *n3=new Node(3);
   Node *n4=new Node(4);
   Node *n5=new Node(5);
   Node *n6=new Node(6);
   Node *n7=new Node(7);
   head=n1;
   n1->next=n2;
   n1->any=n3;
   n2->next=n3;
   n2->any=n4;
   n3->next=n4;
   n4->next=n5;
   n5->any=n7;
   n5->next=n6;
   n6->next=n7;
   n7->next=NULL;
   return head;
}
void FreeList(Node *head)//将链表空间释放
{
	if(head==NULL)
	{
		return ;
	}
	else
	{
		Node *temp=head->next;
		delete head;
		head=temp;
		FreeList(head);
	}
}
void VisitList(Node *head)//遍历链表中的元素,用递归的方法遍历
{
	if(!head) return ;
	Node *p=head;
	while(p)
	{
		cout<<"("<<p->value;
		if(p->any)//记住NULL永远没有NULL
		{
			cout<<","<<p->any->value<<")";
		}
		else
		{
			cout<<",nil)";
		}
		if(p->next)
		{
			cout<<"->";
		}
		p=p->next;
	}
	cout<<endl;
}
void ConnectNode(Node *head)//将每个节点依次复制，并连接使得1->1->2->2->3->3->4->4->5->5->6->6
{
	if(!head) return;
	Node *p=head;
	while(p)
	{
		Node *temp=new Node(p->value);//将当前结点复制
		temp->next=p->next;//连接后继结点
		p->next=temp;//重新设置当前结点的后继结点
		p=p->next->next;
	}
}
void ConnectAny(Node *head)//复制每一个结点的any指针
{
	if(!head) return ;
	Node *p=head;
	while(p)
	{
		if(p->any)//必须保证any指针指向的结点不为NULL，否则会报错，因为NULL永远没有next指针
		{
			p->next->any=p->any->next;
		}
		p=p->next->next;//p每次走两格
	}
}
Node *Separate(Node *head)//将原型结点与复制结点分开
{
	if(!head) return NULL;
	Node *p=head;
	Node *head1=head->next;
	while(p->next)//倒数第二个结点对应原型链表的最后一个结点
	{
		Node *temp=p->next;
		p->next=p->next->next;//这个能够保证间隔连接
		p=temp;//继续扫描吧
	}
	return head1;
}
Node *Clone(Node *head)//用hash法保存any指针
{
	if(!head) return NULL;
	ConnectNode(head);
	ConnectAny(head);
	return Separate(head);
}

int main()
{
	Node *head=CreateList();
	cout<<"原链表输出为:";
	VisitList(head);
	
	cout<<endl<<"复制并连接每个结点:"<<endl;
	ConnectNode(head);
	VisitList(head);

	cout<<endl<<"复制原来每个结点的any指针:"<<endl;
	ConnectAny(head);
	VisitList(head);

        cout<<endl<<"--将复制链表与原型链表分开--"<<endl;
	Node *head1=Separate(head);
	cout<<"输出原型链表:"<<endl;
	VisitList(head);
	cout<<"输出复制链表:"<<endl;
	VisitList(head1);

	cout<<"将以上步骤组合起来，输出复制后的链表:"<<endl;
	head1=Clone(head);
	VisitList(head1);
	FreeList(head);//释放链表空间
	return 0;
}