欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

复杂链表的复制

程序员文章站 2022-06-11 20:30:52
...

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

题目的意思可以简化,就是一个节点含有两个指针和一个数据。用图表示:
复杂链表的复制

如果要实现复杂链表的复制,我们通常的想法和单链表的复制一样,先按照next进行复制,然后在复制random(注:这种事错误的,不能实现)。为什么不能实现?
我们按照代码来实现一下:

	void Copy错误的示范(CNode *list)
	{
		CNode *cur = list;
		CNode *newNode;
		CNode *result = NULL;	// 指向新链表的第一个结点
		CNode *tail = NULL;	// 指向新链表的最后一个结点

							// 按普通链表的方式复制了一份链表
							// 再按尾插的方式,把新结点插入到新的链表中
		//将单链表按照next进行复制
		for (; cur != NULL; cur = cur->next) {
			// 遍历原链表的每个结点,根据其 data 值,创建新结点	// 遍历原链表的每个结点,根据其 data 值,创建新结点
			newNode = CreateNode(cur->data);
			if (tail != NULL) {
				tail->next = newNode;
			}
			else {
				result = newNode;
			}
			tail = newNode;
		}
		//然后开始复制random
		cur = list;
		for (newNode = result; cur != NULL; newNode = newNode->next) 
		{
			newNode->random = cur->random;
			cur = cur->next;
		}
	}

上面的代码在按next复制都没有问题,但如果再按照random进行复制就会出现问题:
复杂链表的复制

如上图:所以,不能够按照普通复制单链表的方式来复制复杂链表
那么,就要换一种思想:就是如何解决上面的那个问题,就要能够通过老链表的random来找到新链表的random,那我们是不是可以将两个链表连在一起,如下图:
复杂链表的复制

按照这样的链表,我们就能够通过上面的random,来找到下面的random(让上面的random->next就可以了),只要能够复制random,再将这个链表拆开就可以了
总结:

  • 第一步:复制每个节点,让老节点跟在新节点的后面
  • 第二步:复制random newNode->random = oldNode->random->next
  • 第三步:拆分链表
	#include <stdio.h>
	#include <stdlib.h>
	#include <assert.h>
	typedef int DataType;

	typedef struct CNode
	{
		DataType data;
		struct CNode *next;
		struct CNode *random;
	}CNode;

	CNode *CreateNode(DataType data)
	{
		CNode *node = (CNode *)malloc(sizeof(CNode));
		node->data = data;
		node->next = NULL;
		node->random = NULL;
		return node;
	}

	CNode *CListInit()
	{
		CNode *n1 = CreateNode(1);
		CNode *n2 = CreateNode(2);
		CNode *n3 = CreateNode(3);
		CNode *n4 = CreateNode(4);

		n1->next = n2;
		n2->next = n3;
		n3->next = n4;
		n1->random = n3;
		n2->random = n1;
		n3->random = n3;
		return n1;
	}

	void CNodeCopy(CNode *list)
	{
		assert(list);
		CNode *cur = list; //cur指向老节点
		CNode *newNode = NULL;  //newNode指向新节点
		CNode *result = newNode; //result指向新链表的头结点
		//第一步
		while (cur != NULL)
		{
			newNode = CreateNode(cur->data);
			newNode->next = cur->next;
			cur->next = newNode;
			cur = newNode->next;
		}
		cur = list;
		result = list->next;
		//第二步
		while (cur->random != NULL)
		{
			newNode = cur->next;
			newNode->random = cur->random->next;
			cur = newNode->next;
		}
		cur = list;
		newNode = cur->next;
		//第三步
		while (cur != NULL)
		{
			cur->next = newNode->next;
			cur = cur->next;
			if (cur != NULL)
			{
				newNode->next = cur->next;
			}
			newNode = newNode->next;
		}
	}

	void test()
	{
		CNode *CList = CListInit();
		CNodeCopy(CList);
	}

	int main()
	{
		test();
		system("pause");
		return 0;
	}