C语言：到底怎样拷贝复杂链表？

首先，我们来看一下什么是复杂链表？

大家都知道一个链表是有若干节点的，普通链表每个节点都有一个指向后一个节点的 next 指针。而复杂链表说：“我偏要有两个指针！一个指向下一个节点，而另一个.....恩，随便指向我的其中一个节点（包括空节点）吧！”，于是，我们给这个随机指向节点的指针赋予一个名字：random。

所以，复杂链表看起来是这样的：

小伙伴们这时候就想说了：“呀，这不是挺简单的嘛！就遍历一遍链表呗，每次遍历的时候就开辟一个空间，存储对应的数据不就行啦？”哈哈，要是这样想的话就正中复杂链表的下怀了！复杂链表每一个 random 指针都会指向自己一个随机的节点，如果要拷贝这个指针，必须要知道他指向的是哪一个节点。为了知道他指向的是哪一个节点，我们每遍历到一个元素，就再次遍历一遍此链表，看哪个元素的地址是原节点的 random 然后记录一下位置，再应用到我们复制出来的链表每个节点中.........ennnn貌似可行，但是完全没有干劲了！

太烦啦！有没有别的方法呢？下面我们来看一种简单的方法：

 如上图，小伙伴们应该看得出来我要干什么~没错，遍历原链表每一个节点的时候，我们复制此节点，然后把他插入到这个节点的后面，嘿嘿嘿.........

咳咳咳，然后，大家是不是发现一个规律：第一个节点7的 random 指向节点1，那么我们复制的这个节点7，他的 random 是不是应该指向：他前面一个节点 random 指向的节点1的后面一个节点，也就是我们复制的节点1！嗷，嗖嘎，原来每一个复制出来的节点和原节点还有这样一个规律啊！这样我们就可以试着写写代码了。

node * copyRandomList(node * head){
	node * cur=head;
	node * newNode=NULL;

	while(cur!=NULL){
		newNode=(node *)malloc(sizeof(node));//newNode:复制的节点
		newNode->num=cur->num;
		newNode->next=cur->next;
		cur->next=newNode;
		newNode->random=NULL;
		cur=newNode->next;
	}//拷贝节点插入原链表
	newNode=head->next;
	cur=head;
	while(cur!=NULL){
		if(cur->random==NULL){
			newNode->random=NULL;
		}
		newNode->random=cur->random->next;
		cur=newNode->next;
		if(cur==NULL){
			break;
		}
		newNode=cur->next;
	}//修改复制节点中的random
}

现在，每个复制的节点中的 random 都已经准备完毕了，也是时候将两个链表分开了！但是要注意，分开归分开，我们还是要将原来的链表还原的！不然原链表生气了怎么办？这里的思路是遍历链表，每次遍历将复制的节点的 next 指向下一个复制的节点，将原节点的 next 指向下一个原节点,最后返回拷贝链表的头节点。

以下是完整的代码喽，声明一下，最后分离的过程小伙伴们一定要结合画图理解哦，不然各位大脑可能会混乱噢：

node * copyRandomList(node * head){
	node * cur=head;
	node * newNode=NULL;
	node * newhead=NULL;
	while(cur!=NULL){
		newNode=(node *)malloc(sizeof(node));
		newNode->num=cur->num;
		newNode->next=cur->next;
		cur->next=newNode;
		newNode->random=NULL;
		cur=newNode->next;
	}//拷贝节点插入原链表
	newNode=head->next;
	cur=head;
	while(cur!=NULL){
		if(cur->random==NULL){
			newNode->random=NULL;
		}
		newNode->random=cur->random->next;
		cur=newNode->next;
		if(cur==NULL){
			break;
		}
		newNode=cur->next;
	}//修改复制节点中的random
	newhead=head->next;
	cur=head;
	newNode=head;
	while(cur!=NULL){
		cur=cur->next->next;
		if(cur==NULL){
			newNode->next=cur;
			break;
		}
		newNode->next->next=cur->next;
		newNode->next=cur;
		newNode=cur;
	}
	return newhead;
}

好啦，对于这道题目，我就先抛砖引玉啦，如文章中有错误或不足之处，欢迎大家指点纠正~

本文章到此结束~