【数据结构】复杂链表深度拷贝

淩亂°似流年 2022-05-15 06:08 140阅读 0赞

## 一、复杂链表深度拷贝 ##

\#\#\#\#【1】题目：  
已知一个复杂链表，该链表除了有一个指向下一个节点的指针外，还有一个指向任意节点的指针，  
求：  
设计一种方法，拷贝构造该链表  
![70][]

\#\#\#\#【2】算法思路：  
1、使用一个map，将链表的地址映射成一个整数，即给链表的每个节点编号  
2、使用一个vector，将新链表中的节点按照map中的指向指好  
\#\#\#\#【3】代码实现：

#include<iostream>
    #include<vector>
    #include<map>
    using namespace std;
    
    struct RandomList
    {
    	int label;
    	RandomList* next;
    	RandomList* random;
    	RandomList(int x)
    		:label(x)
    		,next(NULL)
    		,random(NULL)
    	{}
    };
    
    class solution
    {
    public:
    	RandomList* CopyRandList( RandomList* head)
    	{
    		map<RandomList*, int> node_map;
    		vector<RandomList*> node_vec;
    
    	    RandomList* ptr = head ;
    	    int  i = 0 ;
    	while(ptr)
    	{
    		node_vec.push_back(new RandomList(ptr->label));
    		node_map[ptr] = i;
    		ptr =ptr->next ;
    		i++;
    	}
    	node_vec.push_back(0);
    	ptr = head;
    	i = 0; 
    	
    	while(ptr)
    	{
    		node_vec[i]->next = node_vec[i+1];
    
    		if(ptr->random )
    		{
    			int id = node_map[ptr->random ];
    			node_vec[i]->random = node_vec[id];
    		}
    		ptr = ptr->next ;
    		i++;
    	}
    	return node_vec[0];
    	}
    };
    int main()
    {
    	RandomList a(1);
    	RandomList b(2);
    	RandomList c(3);
    	RandomList d(4);
    	RandomList e(5);
    
    	a.next = &b;
    	b.next = &c;
    	c.next = &d;
    	d.next = &e;
    	e.next = NULL;
    
    	a.random = &c;
    	b.random = &d;
    	c.random = &c;
    	e.random = &d;
    	d.random = NULL;
    	
    	solution solve;
    	RandomList* result = solve.CopyRandList(&a);
    
    	while(result)
    	{
    		printf("label = [ %d ]    ",result->label );
    
    		if(result->random )
    		{
    			printf("rand = %d\n" ,result->random->label );
    		}
    		else
    		{
    			printf("rand = NULL\n");
    		}
    		result = result->next ;
    	}
    	return 0;
    }

\#\#\#\#【4】结果展示：  
![70 1][]

[70]: /images/20220515/64bad5c63769491fae5d1365451cd046.png
[70 1]: /images/20220515/00ddd09ecd3c41cd8bcb2dbeb7957957.png