复杂链表的复制

复杂链表的复制

一个链表的每个结点，有一个指向next指针指向下一个结点，还有一个random指针指向这个链表
中的一个随机结点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

首先我们先给出这个复杂链表，并将其初始化

代码：

typedef struct  ComplexNode
{
	int data;//数据域
	struct ComplexNode *next;//指向下一个元素
	struct ComplexNode *random;//指向随机元素
}CN;
CN *CreateNode(int data)
{
	CN *node = (CN*)malloc(sizeof(CN));
	node->data = data;
	node->random = node->next = NULL;
	return node;
}
CN *InitCN()
{//初始化如上图
	CN *n1 = CreateNode(1);
	CN *n2 = CreateNode(2);
	CN *n3 = CreateNode(3);
	CN *n4 = CreateNode(4);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n1->random = n3;
	n2->random = n1;
	n3->random = n3;
	return n1;
}

这时候我们可以看到在内存中已经初始化好了

接下来就是复制了，如果我们按照常规复制链表的话，无法复制random结点，这里复制的难点>主要是random的复制，如何根据老结点的random找到新结点的random，我们可以让每个新结点>都跟在老结点的后面。

代码如下：

void Copy(CN *list)
{
	CN *cur = list;
	CN *newnode;
	//复制每个结点（只复制data），让新结点跟在老结点后面
	while (cur != NULL)
	{
		newnode = CreateNode(cur->data);
		newnode->next = cur->next;
		cur->next = newnode;
		cur = newnode->next;
	}
	//复制random字段
	cur = list;
	while (cur != NULL)
	{
		newnode = cur->next;
		if (cur->random != NULL)
		{
			newnode->random = cur->random->next;
		}
		cur = cur->next->next;
	}
	//把一个链表拆成两个链表
	cur = list;
	CN *next;
	CN *newnext;
	CN *result = list->next;
	while (cur != NULL)
	{
		newnode = cur->next;
		next = newnode->next;
		if (next == NULL)
		{
			newnext = NULL;
		}
		else
		{
			newnext = next->next;
		}
		cur->next = next;
		newnode->next = newnext;
		cur = next;
	}
	printf("复制成功\n");
}