题目：一个链表的每个节点，有一个指向next指针指向先一个节点，还有一个random指针指向这个链表的一个随机节点或者NULL，现在要求实现复制这个复杂的链表，返回复制后的新链表。

复杂链表的结构

template
     
      struct ComplexNode{public:	ComplexNode(const T& data)		:_data(data)		,_next(NULL)		,_random(NULL)	{}public:	T _data;//数据	ComplexNode* _next;//指向下一个节点	ComplexNode* _random;//指向随机节点（可以是链表中的任意节点或者空）};
     

思路分析：

看到这道题目时，最常规的思路就是，要分成两步。首先要复制原来单链表上的每一个结点并且连接起来。最后将单链表的random指针更改。

更改random的时候有两种解决方法：

1）更改每个结点的时候都记录下该结点的位置，即第几个，通过计数器更改。

对一个含有n个结点的链表，由于定位每个结点的_random，都需要从链表头结点开始经过O(n)步才能找到，因此这种方法的总时间复杂度是O(n2)。

评价：时间复杂度太太。

2）由于上述方法的时间主要花费在定位结点的_random上面，我们试着在这方面去做优化。这里我们对<N，N’>的配对信息放到一个哈希表中。设置复制链表上每个结点的_random。如果在原始链表中结点N的_random指向结点S，那么在复制链表中，对应的N’应该指向S’。由于有了哈希表，我们可以用O(1)的时间根据S找到S’。

评价：用空间换时间，以O(n)的空间消耗实现了O(n)的时间效率。

接着我们来换一种思路，在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N，创建对应的N’。这一次，我们把新创建的每个结点N’链接在原先结点N的后面。

最后，将整个链表拆分成原始链表和拷贝出的链表。

实现代码：

template
     
      struct ComplexNode{public:	ComplexNode(const T& data)		:_data(data)		,_next(NULL)		,_random(NULL)	{}public:	T _data;//数据	ComplexNode* _next;//指向下一个节点	ComplexNode* _random;//指向随机节点（可以是链表中的任意节点或者空）};template
      
       void CloneListNode(ComplexNode
       
        * pHead)//复制链表节点并连接在该节点的后边{	if (pHead)//链表不为空	{		ComplexNode
        
          * cur = pHead;		while (cur)		{			ComplexNode
         
          * NewNode = new ComplexNode
          
           (cur->_data); NewNode->_next = cur->_next; cur->_next = NewNode; cur = NewNode->_next;//下一个未被复制的节点 } }}template
           
            void ConnectionNode(ComplexNode
            
             * pHead)//更新新节点的随机指针{ if (pHead)//链表不为空 { ComplexNode
             
               * cur = pHead; while (cur) { ComplexNode
              
                * Random = cur->_random;//随机节点 if (Random)//随机节点可能为空 { Random = cur->_random; cur->_next->_random = Random->_next;//将随机指针复制 } cur = cur->_next->_next;//节点向后移动 } }}template
               
                ComplexNode
                
                 * ReconnectNodes(ComplexNode
                 
                  * pHead)//将原来链表产分为两个{ ComplexNode
                  
                   * newHead = NULL; ComplexNode
                   
                    * first = pHead;//原来的链表 ComplexNode
                    
                     * second = newHead;//新的链表 if (pHead!=NULL)//链表不为空 { newHead = first->_next; second = newHead; first = first->_next; } while (first)//遍历链表 { second->_next = first->_next; second = second->_next; if (second)//防止空指针的引用 { first->_next = second->_next; } first = first->_next; } return newHead;}template
                     
                      ComplexNode
                      
                       *  CopyList(ComplexNode
                       
                        * pHead){ if (pHead)//链表不为空 { CloneListNode(pHead);//克隆节点并且连在该节点的后边 ConnectionNode(pHead);//连接 ComplexNode
                        
                         * NewHead = ReconnectNodes(pHead);//拆分 return NewHead; } return NULL;}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

创建复杂的链表

template
     
      void CreateList(ComplexNode
      
       * &pHead)//复杂链表的建立{	ComplexNode
       
         *Node1 = new ComplexNode
        
         ('A');	ComplexNode
         
           *Node2 = new ComplexNode
          
           ('B'); ComplexNode
           
             *Node3 = new ComplexNode
            
             ('C'); ComplexNode
             
               *Node4 = new ComplexNode
              
               ('D'); ComplexNode
               
                 *Node5 = new ComplexNode
                
                 ('E'); pHead = Node1; Node1->_next = Node2; Node2->_next = Node3; Node3->_next = Node4; Node4->_next = Node5; Node1->_random = Node3; Node2->_random = Node4; Node3->_random = Node5; Node4->_random = Node1; Node5->_random = Node2;}
                
               
              
             
            
           
          
         
        
       
      
     

打印复杂链表

template
     
      void PrintList(ComplexNode
      
       * pHead)//打印复杂链表{	if (pHead)//链表不为空	{		ComplexNode
       
         * cur = pHead;		while (cur)		{			cout << "(" << cur->_data << " " << cur->_random->_data << ")" << "->";			//注意随机指针可能为空，不指向任何数据，此时会导致空指针的简引用，此处为了测试效果，所以复杂链表中没有指向空指针			cur = cur->_next;		}		cout<<"over" << endl;	}}
       
      
     

测试函数

template
     
      void test(){	ComplexNode
      
       * _head;	CreateList(_head);	cout << "原来的链表:";	PrintList(_head);	cout << "复制的链表:";	PrintList(CopyList(_head));}
      
     

测试结果：