复杂链表与单链表

首先呢，得告诉大家【复杂链表】和【普通链表】的一些区别

可是这个不怎么好描述

不过呢，我请来了【四个小学生】，来帮助大家理解

小时候的小A、小B、小C和小D

我们有四个同学 A、B、C、D

他们【高高兴兴】的排起了队

他们依次站着，无所他想，每个人只记住后面那个人，那么队伍就不会分散

小A、小B、小C和小D的成长

原本安安分分的A、B、C和D都长大了

他们之间有的迸发出了【爱情的火花】

彼此之间会不会@H_403_125@【闹出矛盾】？？？

【友谊的小船】会不会说翻就翻？？

在小A、小B、小C和小D的成长过程中

他们发现了【爱情】这个东西

小A：喜欢上了小C

小C：却喜欢小B

小B：表示@H_403_125@【无可奈何】，我不想趟这趟浑水（怕小A报复）

小D：作为一只@H_403_125@【单身狗】，我表示爱自己就好

现在，问题来了，请读者解答

1、上面四个好朋友中出现了【几角恋】？

2、B为什么拒绝了C

好了，是不是很混乱呢，甚至有点晕乎

那么这就对了，这就是【复杂链表】

复杂链表的定义

在链表的结构体中，除了有一个指向【下个节点】（后面那个人）的【指针】

还有一个指向【链表自身】中【任意节点（或者NULL）】的【指针】

那么这个链表就叫【复杂链表】

复杂链表的处理

复杂链表的构造（完整版代码在最后）

结构体：

typedef struct DNode
{
	int data;
	struct DNode* next;
	struct DNode* random;
}DNode,*PDNode;

申请一个节点：

PDNode BuyNewNode(int data)
{
	PDNode NewNode = (PDNode)malloc(sizeof(DNode));
	if (NewNode == NULL)
	{
		return NULL;
	}
	NewNode->data = data;
	NewNode->next = NULL;
	NewNode->random = NULL;
	return NewNode;
}

构建一个如题所示的复杂链表：

PDNode MakeDiffList()
{
	PDNode pHead = NULL;
	PDNode CurNode = NULL;
	PDNode NewNode = BuyNewNode(1);
	PDNode Node1,Node2,Node3,Node4 = NULL;//把四个节点都保存起来，好表示他们【长大后】的“暗恋”关系
	pHead = NewNode;
	CurNode = pHead;
	Node1 = CurNode;

	NewNode = BuyNewNode(2);//NULL
	CurNode->next = NewNode;
	CurNode = CurNode->next;
	Node2 = CurNode;

	NewNode = BuyNewNode(3);//2
	CurNode->next = NewNode;
	CurNode = CurNode->next;
	Node3 = CurNode;

	NewNode = BuyNewNode(4);//自己
	CurNode->next = NewNode;
	CurNode = CurNode->next;
	Node4 = CurNode;

	Node1->random = Node3;//小A 暗恋 小C
	Node2->random = NULL;//小B 谁都不恋
	Node3->random = Node2;//小C 暗恋 小B
	Node4->random = Node4;//小D 爱 自己
	
	return pHead;
}

这样我们的复杂链表就够造好啦~~~

复杂链表的复制

（1）首先，是原来的链表

（2）然后我们还是首先复制每一个结点N为N*，并且让N*在对应的N后面，即为

注意：复制的过程中，love指针不能直接复制

比如 【A‘】指向的是 【C】 而不是 【C'】

我们应当指向 【A->love->next】 通过C的下一个来找到 【C'】

（3）最后，将产生的新的复杂链表删除~大工搞成

复制复杂链表的代码：

PDNode CopyDiffList(PDNode*pHead)
{
	PDNode CurNode = *pHead;
	PDNode NewHead = NULL;
	PDNode NewNode = NULL;
	if (pHead == NULL)
	{
		return NULL;
	}
	/**************首次复制并连接*********************/
	while (CurNode!=NULL)
	{
		//NewNode = BuyNewNode(CurNode->data*11);//测试中用11 倍的数据，方便调试
		NewNode = BuyNewNode(CurNode->data);
		
		NewNode->next = CurNode->next;
		NewNode->random = CurNode->random;
		CurNode->next = NewNode;

		CurNode = NewNode->next;
	}
	/*************************************************/

	/**************进行random的移动*******************/
	CurNode = *pHead;
	while (CurNode!= NULL)
	{
		if (CurNode->random != NULL)
			CurNode->next->random = CurNode->random->next;
		CurNode = CurNode->next->next;
	}
	/*************************************************/

	/****************删除原来的元素*******************/
	CurNode = *pHead;
	NewHead = (*pHead)->next;
	NewNode = (*pHead)->next;
	while (CurNode->next->next!= NULL)
	{
		CurNode->next =  NewNode->next; 
		NewNode->next = NewNode->next->next;

		CurNode = CurNode->next;
		NewNode = NewNode->next;

	}
	NewNode->next = NULL;
	CurNode->next = NULL;
	/*************************************************/

	return NewHead;

}

完整版代码：

//结构体
typedef struct DNode
{
	int data;
	struct DNode* next;
	struct DNode* random;
}DNode,*PDNode;


//生成一个新节点并返回
PDNode BuyNewNode(int data)
{
	PDNode NewNode = (PDNode)malloc(sizeof(DNode));
	if (NewNode == NULL)
	{
		return NULL;
	}
	NewNode->data = data;
	NewNode->next = NULL;
	NewNode->random = NULL;
	return NewNode;
}

//构造复杂链表
PDNode MakeDiffList()
{
	PDNode pHead = NULL;
	PDNode CurNode = NULL;
	PDNode NewNode = BuyNewNode(1);
	PDNode Node1,Node4 = NULL;
	pHead = NewNode;
	CurNode = pHead;
	Node1 = CurNode;

	NewNode = BuyNewNode(2);//NULL
	CurNode->next = NewNode;
	CurNode = CurNode->next;
	Node2 = CurNode;

	NewNode = BuyNewNode(3);//2
	CurNode->next = NewNode;
	CurNode = CurNode->next;
	Node3 = CurNode;

	NewNode = BuyNewNode(4);//自己
	CurNode->next = NewNode;
	//CurNode->random = CurNode;
	CurNode = CurNode->next;
	Node4 = CurNode;

	Node1->random = Node3;
	Node2->random = NULL;
	Node3->random = Node2;
	Node4->random = Node4;
	
	return pHead;
}

//复制复杂链表
PDNode CopyDiffList(PDNode*pHead)
{
	PDNode CurNode = *pHead;
	PDNode NewHead = NULL;
	PDNode NewNode = NULL;
	if (pHead == NULL)
	{
		return NULL;
	}
	/*****************首次复制并连接******************/
	while (CurNode!=NULL)
	{
		//NewNode = BuyNewNode(CurNode->data*11);//测试中用11 倍的数据，方便调试
		NewNode = BuyNewNode(CurNode->data);
		
		NewNode->next = CurNode->next;
		NewNode->random = CurNode->random;
		CurNode->next = NewNode;

		CurNode = NewNode->next;
	}
	/*************************************************/

	/**************进行random的移动*******************/
	CurNode = *pHead;
	while (CurNode!= NULL)
	{
		if (CurNode->random != NULL)
			CurNode->next->random = CurNode->random->next;
		CurNode = CurNode->next->next;
	}
	/*************************************************/

	/****************删除原来的元素*******************/
	CurNode = *pHead;
	NewHead = (*pHead)->next;
	NewNode = (*pHead)->next;
	while (CurNode->next->next!= NULL)
	{
		CurNode->next =  NewNode->next; 
		NewNode->next = NewNode->next->next;

		CurNode = CurNode->next;
		NewNode = NewNode->next;

	}
	NewNode->next = NULL;
	CurNode->next = NULL;
	/*************************************************/

	return NewHead;

}

//进行测试
void FunTest()
{
	PDNode pHead = NULL;
	PDNode pNewHead = NULL;
	pHead = MakeDiffList();
	pNewHead = CopyDiffList(&pHead);
	return;
}

//主函数
int main()
{
	FunTest();
	return 0;
}

皓皓有话说：

问：如何在众多课程的压力下继续看书呢？

Linux、C++primer

还有杨老师给我提示的如何预习Java（异常、继承、正则表达式等....）

挤一挤时间总会有的，下课时间十分钟的【休闲时光】也要搭进去喽~

原文链接：https://www.f2er.com/datastructure/382450.html