复杂链表的复制

程序员文章站 2022-06-11 20:16:04

...

复杂链表的复制：

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

解析：复杂链表的复制可以分成三部分

（1）在原链表的每个节点后插入值相等的新节点

（2）给新节点的随机指针域赋值

（3）将链表从原链表上拆下

看代码：

#include<windows.h>
#include<stdio.h>
typedef int DataType;
typedef struct Node
{
	DataType data;
	struct Node* random;
	struct Node* next;
}Node, *pNode, List, *pList;
pNode BuyNode(DataType d)
{
	pNode p = malloc(sizeof(Node));
	p->data = d;
	p->next = NULL;
	return p;
}
pNode first(pList *s)//（1）在原链表的每个节点后插入值相等的新节点  
{
	pList phead = *s;
	pList cur = *s;
	while (cur != NULL)
	{
		pNode Newnode = BuyNode(cur->data);
		Newnode->next = cur->next;
		cur->next = Newnode;

		cur = Newnode->next;
	}
	return phead;
}
pNode second(pList *s)//（2）给新节点的随机指针域赋值        
{
	pList phead = *s;
	pList cur = *s;
	while (cur != NULL)
	{
		pNode Newnode = cur->next;
		if (cur->random == NULL)
			Newnode->random = NULL;
		else
			Newnode->random = cur->random;
		cur = Newnode->next;
	}
	return phead;
}
pNode third(pList *s)//（3）将链表从原链表上拆下
{
	pList phead = *s;
	pList Newhead = phead->next;
	pList cur = phead->next;
	while (cur!= NULL)
	{
		phead->next = phead->next->next;
		if (cur->next != NULL)
			cur->next = cur->next->next;
		phead = phead->next;
		cur = cur->next;
	}
	return Newhead;
}

void CopyComplexList()
{
	pNode s1 = BuyNode(1);
	pNode s2 = BuyNode(2);
	pNode s3 = BuyNode(3);
	pNode s4 = BuyNode(4);

	s1->next = s2;

	s2->next = s3;

	s3->next = s4;

	s4->next = NULL;

	s1->random = s3;
	s2->random = s4;
	s3->random = s3;
	s4->random = NULL;
	first(&s1);
	second(&s1);
	pNode NewPhead = third(&s1);
}
int main()
{
	CopyComplexList();
	system("pause");
	return 0;
}

图解：（1）创建一个复杂链表，如下图：

复杂链表的复制