c语言—复杂链表的复制

所谓复杂链表，指的是链表中每个节点不仅有指向下一个节点的next指针，还有一个radom指针指向一个随机节点，甚至可以指向自己，可以指向空。

typedef struct ListNode
{
	DataType data;
	struct ListNode* next;   //next指向下一个节点
	struct ListNode* radom;  //radom指向随机节点
}ListNode;

所以复杂链表的复制考虑的因素就比较多，经过九九八十一难，我实现了这个功能。

最开始我是这样认为的：

这是不对的，如果有链表中有相同的data，那就一定会出错。

所以最好的办法是：

ListNode* CopyList(ListNode* head)
{
	//1.插入节点  1 1 2 2 3 3 4 4 ……
	ListNode* cur = head;
	while(cur)
	{
		ListNode* next = cur->next;
		ListNode* copy = BuyNode(cur->data);
		cur->next = copy;
		copy->next = next;
		cur = next;
	}

	//2.这样的话，拷贝的节点的radom一定在被拷贝的节点的radom的后面
	cur = head;
	while(cur)
	{
		ListNode* copy = cur->next;
		if(cur->radom != NULL)
		{
			copy->radom = cur->radom->next;
		}
		cur = copy->next;
	}

	//3.把新旧链表拆开，先拆一个节点当头
	cur = head;
	ListNode* copyHead = NULL;//作新链表的头
	ListNode* copyTail = NULL;//作新链表的尾

	while(cur)
	{
		ListNode* copy = cur->next;
		ListNode* next = copy->next;

		cur->next = next;

		if(copyHead == NULL)
		{
			copyHead = copy;
			copyTail = copy;
		}

		else
		{
			copyTail->next = copy;
			copyTail = copy;
		}

		cur = next;
	}

	return copyHead;
}

其中，BuyNode函数是这样的：

ListNode* BuyNode(DataType data)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	assert(node);
	node->data = data;
	node->next = NULL;
	node->radom = NULL;
	return node;
}

以下是测试代码，这样写易于测试程序的对错：

void test()
{
	ListNode* node1 = BuyNode(1);
	ListNode* node2 = BuyNode(2);
	ListNode* node3 = BuyNode(3);
	ListNode* node4 = BuyNode(4);

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;

	node1->radom = node2;
	node2->radom = NULL;
	node3->radom = node3;
	node4->radom = node1;   //1->2  2->NULL  3->3  4->1

	ListNode* test = CopyList(node1);
}

通过验证，程序正确。