带有随机指针链表的复制

曾经终败给现在 2022-02-17 05:42 163阅读 0赞

## 链表复制 ##

上次介绍了关于链表的相交与求环问题，这次我来给大家介绍一个让我脑瓜子嗡嗡的复杂链表的复制问题。。 说实话，链表也太狂野了，太会玩了，都快赶上苏大强了。。。。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
我的个天，画了半天，别介意，本人画画水平不是特别高，大家凑合看。如上图所示，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。现在要求返回这个链表的深拷贝。这该怎么办呢，一开始我也一头雾水，这是个啥啊，看半天也没看懂，最后看是看明白了，但是不会做，这就尴尬了，我当时就比较疑惑的是怎么根据原有链表的形式复制新链表，要创建新链表就要创建节点，假如我们第一个链表的节点的随机指针指向最后一个节点怎么办，我这还没有创建好最后一个节点。。。。 也许你会说那我们可以先根据原有链表创建好新链表，先不管随机指针，创建好在复制我们的随机指针，但是，但是，但是，我们的随机指针指向的是随机的节点，我们如何去改变随机指针的指向呢？ 哎呀，头大了，，，，，  
想了半天也不知道从何下手，最后经由大佬指点，便有了下面这种思路。。

*  1、我们可以将创建的新节点并插入放在老节点的后面，让他们串起来  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1]  
    2、创建成功后现在根据原有的链表就可以很方便的复制随机指针了  
    3、最后将我们的链表分离出来，就得到了所求的链表

是不是很神奇，很惊喜！！！ 哈哈，其实我也没想到原来还可以这样操作，如果你还是不太明白的话，下面咱们上代码，或许你看看代码就懂了

#include<iostream>
    using namespace std;
    
    class Node {
    public:
    	int val;
    	Node* next;
    	Node* random;
    
    	Node() {}
    
    	Node(int _val, Node* _next, Node* _random) {
    		val = _val;
    		next = _next;
    		random = _random;
    	}
    };
    
    
    void Print(Node* head) {
    	Node* cur = head;
    	while (cur != NULL) {
    		printf("%p(%d)-->  ", cur, cur->val);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    //复制随机链表
    Node* CopyRandomList(Node* head)
    {
    	if (head == NULL) {
    		return NULL;
    	}
    	//创建新节点，插入到旧节点后面
    	Node* cur = head;
    	while (cur != NULL) {
    		Node* node = (Node*)malloc(sizeof(Node));
    		node->val = cur->val;
    		node->next = cur->next;
    		cur->next = node;
    		node->random = NULL;
    		cur = node->next;
    	}
    	// 插入成功，复制random指针
    	cur = head;
    	while (cur != NULL)	{
    		if (cur->random != NULL) {
    			cur->next->random = cur->random->next;
    		}
    		cur = cur->next->next;
    	}
    	//拆分链表
    	cur = head;
    	Node* newHead = cur->next;
    	while (cur != NULL) {
    		Node* nn = cur->next;
    		cur->next = nn->next;
    		if (nn->next != NULL) {
    			nn->next = cur->next->next;
    		}
    		cur = cur->next;
    	}
    	return newHead;
    }
    
    Node* CreateNode(int val) {
    	Node* node1 = (Node*)malloc(sizeof(Node));
    	node1->val = val;
    	return node1;
    }
    
    
    int main()
    {
    	Node* node1 = CreateNode(1);
    	Node* node2 = CreateNode(2);
    	Node* node3 = CreateNode(3);
    	Node* node4 = CreateNode(4);
    	node1->next = node2; node1->random = node3;
    	node2->next = node3; node2->random = node1;
    	node3->next = node4; node3->random = node3;
    	node4->next = NULL; node4->random = NULL;
    	Print(node1);
    	Node* newHead = CopyRandomList(node1);
    	Print(newHead);
    	system("pause");
    	return 0;
    }

其实在我看来关于链表相关的问题，重在画图，因为大部分人在大脑中是很难构建出来这个过程的。对于这个问题而言，我觉得还蛮有意思的，虽然自己很菜，没想出解决方案来，但我相信也许大家还会有好的方法，天马行空的思路来解决这个问题，还请不吝赐教，，， 让我也膜拜一下！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220217/ba97af93963042ac92e8bce481235b9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1]: /images/20220217/8692bb3b83ab428aa6ba8231e87ba479.png