首页 > 试题广场 >

复杂链表的复制

[编程题]复杂链表的复制
  • 热度指数：770704 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分，3，5，#，2，#分别的表示为
1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null
如下图:

示例1

输入

{1,2,3,4,5,3,5,#,2,#}

输出

{1,2,3,4,5,3,5,#,2,#}

说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
crazychen头像 crazychen 
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode p = pHead;
        RandomListNode q = new RandomListNode(-1);
        while(p!=null){
            RandomListNode t = new RandomListNode(p.label);
            map.put(p, t);
            p = p.next;
            q.next = t;
            q = t;
        }
        Set<Entry<RandomListNode,RandomListNode>> set = map.entrySet();        
        Iterator<Entry<RandomListNode,RandomListNode>> it = set.iterator();        
        while(it.hasNext()){
            Entry<RandomListNode, RandomListNode> next = it.next();            
            next.getValue().random = map.get(next.getKey().random);
        }
        return map.get(pHead);
    }
}
发表于 2015-04-11 22:13:33 回复(15)
treasuresss头像 treasuresss
方法一：map关联
    首先遍历一遍原链表，创建新链表（赋值label和next），用map关联对应结点；再遍历一遍，更新新链表的random指针。（注意map中应有NULL ----> NULL的映射）

方法二：next指针关联
    创建新链表的时候，用原结点的next指针指向对应新结点，新结点的next指针指向下一个原结点，以此类推，形成之字形关联。然后，就可以先更新新链表的random指针，再解除next关联，更新next指针。这种方法不需要map来辅助，不管查找next还是random指针都是O(1)的，效率很高。

最后附上代码！ 

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
    	if(pHead==NULL) return NULL;

    	map<RandomListNode*,RandomListNode*> m;
    	RandomListNode* pHead1 = pHead;
        RandomListNode* pHead2 = new RandomListNode(pHead1->label);
        RandomListNode* newHead = pHead2;
        m[pHead1] = pHead2;
        while(pHead1){
        	if(pHead1->next) pHead2->next = new RandomListNode(pHead1->next->label);
        	else pHead2->next = NULL;
        	pHead1 = pHead1->next;
        	pHead2 = pHead2->next;
        	m[pHead1] = pHead2;
        }

        pHead1 = pHead;
        pHead2 = newHead;
        while(pHead1){
        	pHead2->random = m[pHead1->random];
        	pHead1 = pHead1->next;
        	pHead2 = pHead2->next;
        }
        return newHead;
    }
};


class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
    	if(pHead==NULL) return NULL;

        RandomListNode *newHead = new RandomListNode(pHead->label);
    	RandomListNode *pHead1=NULL, *pHead2=NULL;

        // 上链，使新旧链表成之字形链接
        for(pHead1=pHead,pHead2=newHead;pHead1;){
        	RandomListNode* tmp = pHead1->next;
        	pHead1->next = pHead2;
        	pHead2->next = tmp;

        	// next
        	pHead1 = tmp;
        	if(tmp) pHead2 = new RandomListNode(tmp->label);
        	else pHead2 = NULL;
        }

        // 更新新链表的random指针
        for(pHead1=pHead,pHead2=newHead;pHead1;){
        	if(pHead1->random) pHead2->random = pHead1->random->next;
        	else pHead2->random = NULL;

        	pHead1 = pHead2->next;
        	if(pHead1) pHead2 = pHead1->next;
        	else pHead2 = NULL;
        }

        // 脱链，更新各链表的next指针
        for(pHead1=pHead,pHead2=newHead;pHead1;){
        	pHead1->next = pHead2->next;
        	if(pHead1->next) pHead2->next = pHead1->next->next;
        	else pHead2->next = NULL;

        	pHead1 = pHead1->next;
        	pHead2 = pHead2->next;
        }

        return newHead;
    }
};

编辑于 2015-11-12 11:23:57 回复(6)
Python
华科平凡头像 华科平凡

python两种解法

递归法：

class Solution:
    def Clone(self, head):
        if not head: return
        newNode = RandomListNode(head.label)
        newNode.random = head.random
        newNode.next = self.Clone(head.next)
        return newNode

哈希表法：

class Solution:
    def Clone(self, head):
        nodeList = []     #存放各个节点
        randomList = []   #存放各个节点指向的random节点。没有则为None
        labelList = []    #存放各个节点的值

        while head:
            randomList.append(head.random)
            nodeList.append(head)
            labelList.append(head.label)
            head = head.next
        #random节点的索引，如果没有则为1    
        labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList)

        dummy = RandomListNode(0)
        pre = dummy
        #节点列表，只要把这些节点的random设置好，顺序串起来就ok了。
        nodeList=map(lambda c:RandomListNode(c),labelList)
        #把每个节点的random绑定好，根据对应的index来绑定
        for i in range(len(nodeList)):
            if labelIndexList[i]!=-1:
                nodeList[i].random=nodeList[labelIndexList[i]]
        for i in nodeList:
            pre.next=i
            pre=pre.next
        return dummy.next
发表于 2017-10-21 14:02:09 回复(29)
马客(Mark)头像 马客(Mark)
因为题目上说random指向任意节点，不知道这个random指向的节点是否一定在链表中，所以直接当做一个有向图来做了，做法大同小异。 

class Solution {
    map<RandomListNode*, RandomListNode*> mp;
    set<RandomListNode*> vis;
    void dfs1(RandomListNode* u){
        if(u && mp.find(u) == mp.end()) {
            mp[u] = new RandomListNode(u -> label);
            dfs1(u -> next);
            dfs1(u -> random);
        }
    }
    void dfs2(RandomListNode* u){
        if(u && vis.find(u) == vis.end()){
            if(u -> next) mp[u] -> next = mp[u -> next];
            if(u -> random) mp[u] -> random = mp[u -> random];
            vis.insert(u);
            dfs2(u -> next);
            dfs2(u -> random);
        }
    }
public:
    RandomListNode* Clone(RandomListNode* pHead){
        if(!pHead) return NULL;
        mp.clear();
        vis.clear();
        dfs1(pHead);
        dfs2(pHead);
        return mp[pHead];
    }
};

发表于 2015-08-23 01:16:48 回复(11)
Java
江南消夏头像 江南消夏
方法一：递归思想 
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) return null;
        
        RandomListNode newNode = new RandomListNode(pHead.label);
        
        newNode.random = pHead.random;
        newNode.next = Clone(pHead.next);
        
        return newNode;
    }
}
方法二：复制再拆分 

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) return null;
        
        RandomListNode pCur = pHead;
        while (pCur != null)
        {
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;
            pCur = node.next;
        }
        
        pCur = pHead;
        while (pCur!=null)
        {
            if (pCur.random!=null)
                pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        
        RandomListNode head = pHead.next;
        RandomListNode tmp = head;
        pCur = pHead;
        while(pCur.next!=null)
        {
            tmp = pCur.next;
            pCur.next = tmp.next;
            pCur = tmp;
        }
        return head;
    }
}

编辑于 2017-01-04 10:59:42 回复(11)
ToddHu头像 ToddHu
1.利用空间节省时间（引入hashmap，然后在查找random的时候就可以直接从hashmap中查找对应的节点）时间复杂度O(n)。 

	/*





	public class RandomListNode {





	    int label;





	    RandomListNode next = null;





	    RandomListNode random = null;





	 





	    RandomListNode(int label) {





	        this.label = label;





	    }





	}





	*/





	importjava.util.HashMap;





	publicclassSolution {





	    publicRandomListNode Clone(RandomListNode pHead)





	    {





	        if(pHead == null) returnnull;





	        HashMap<RandomListNode, RandomListNode> map = newHashMap<RandomListNode, RandomListNode>();





	        RandomListNode newHead = newRandomListNode(pHead.label);





	        RandomListNode pre = pHead, newPre = newHead;





	        map.put(pre, newPre);





	         





	        while(pre.next != null){





	            newPre.next = newRandomListNode(pre.next.label);





	            pre = pre.next;





	            newPre = newPre.next;





	            map.put(pre, newPre);





	        }





	        pre = pHead;





	        newPre = newHead;





	        while(newPre != null){





	            newPre.random = map.get(pre.random);





	            pre = pre.next;





	            newPre = newPre.next;





	        }





	        returnnewHead;





	    }





	}
2.如何在不利用hashmap的情况下，实现O(n)的算法 

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        
        if(pHead == null) return null;
        RandomListNode node = pHead;
        //复制节点，并放在源节点之后
        while(node != null ){
            RandomListNode newNode = new RandomListNode(node.label);
            newNode.label = node.label;
            newNode.next = node.next;
            newNode.random = null;
            node.next = newNode;
            node = newNode.next;
        }
        //复制random指向复制后的节点
        node = pHead;
        while(node != null){
            RandomListNode newNode = node.next;
            if(node.random != null){
           		newNode.random = node.random.next;
            }
            node = newNode.next;
        }
        //获取新的链表
        RandomListNode newHead = null;
        RandomListNode cloneNode = null;
        RandomListNode pNode = pHead;
        if(pNode != null){
            newHead = pNode.next;
            cloneNode = pNode.next;
            pNode.next =  cloneNode.next;
            pNode = pNode.next;
        }
        
        while(pNode != null){
            cloneNode.next = pNode.next;
            cloneNode = cloneNode.next;
            pNode.next = cloneNode.next;
            pNode = pNode.next;
        }
        return newHead;
    }
    
}

发表于 2016-06-03 16:13:20 回复(4)
Java
chancy头像 chancy 
/*
*解题思路：
*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }
        
        RandomListNode currentNode = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while(currentNode != null){	
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }
        
        currentNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while(currentNode != null) {
            currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
            currentNode = currentNode.next.next;
        }
        
        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while(currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            currentNode = currentNode.next;
        }
        
        return pCloneHead;
    }
}
编辑于 2017-03-11 17:39:20 回复(101)
大闲人柴毛毛头像 大闲人柴毛毛
1. 复制单链表
    1.1. p指向头结点，只要p不为空，就一直循环；
    1.2. 创建新节点，值和p相同；
    1.3. 将新节点插入p节点之后；
2. 连接random域
    2.1. p指向头结点；
    2.2. 将含有random的p节点的后继节点添加random域；
    PS：有些节点本身就没有random，再访问random的后继就会出现空指针！
3. 拆分单链表
    3.1. p指向头结点，依次向后移动；
    3.2. 将p指向后继的后继；
    3.3. p的后继指向p的后继的后继的后继；
    PS：若p已经为最后一个元素，则p的后继直接为null，否则出现空指针！
发表于 2017-03-20 14:58:45 回复(0)
TX游戏客户端开发内推头像 TX游戏客户端开发内推 
//C++实现 时间效率O(n) 空间效率为0 最优解法
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectRandomNodes(pHead);
        return Distract(pHead);
    }
    
    //把每一个节点的复制后的节点，连接在每一个后面
    void CloneNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=nullptr)
        {
//构造函数，新开辟空间用于存复制的节点，由于后面没有赋节点给pCloneNode的步骤，所以不能赋值为nullptr
            RandomListNode* pCloneNode=new RandomListNode(0);//label初始化为0
            pCloneNode->label=pNode->label;//此步复制了节点
            pCloneNode->next=pNode->next;
            pCloneNode->random=nullptr;
            
            pNode->next=pCloneNode;
            pNode=pCloneNode->next;
        }
    }
    
    //设置复制出来的节点的random指针
    void ConnectRandomNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=nullptr)
        {
            RandomListNode* pCloneNode=pNode->next;
            if(pNode->random!=nullptr)
                pCloneNode->random=pNode->random->next;
            pNode=pCloneNode->next;
        }
    }
    
    //将一个链表拆分为两个链表,并只返回复制的那个链表
    RandomListNode* Distract(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;//把A赋给pNode
        RandomListNode* pCloneHead=nullptr;
        RandomListNode* pCloneNode=nullptr;
        
        if(pNode!=nullptr)
        {
            pCloneNode=pNode->next;
            pCloneHead=pNode->next;
            pNode->next=pCloneNode->next;//A->B连接
            pNode=pCloneNode->next;//把B赋给pNode
        }
        while(pNode!=nullptr)
        {
            pCloneNode->next=pNode->next;//A'->B'连接
            pCloneNode=pNode->next;//把B‘赋给pCloneNode
            
            pNode->next=pCloneNode->next;//B->C连接 等
            pNode=pCloneNode->next;//把C赋给pNode 等
        }
        return pCloneHead;
    }
};

发表于 2017-08-23 12:24:55 回复(0)
drdr头像 drdr 
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        RandomListNode* curNode = pHead;
        while(curNode!=NULL){
            RandomListNode* newNode = new RandomListNode(curNode->label);
            newNode->next = curNode->next;
            curNode->next = newNode;
            curNode = newNode->next;
        }
        curNode = pHead;
        while(curNode!=NULL){
            if(curNode->random!=NULL)
            	curNode->next->random = curNode->random->next;   
            curNode = curNode->next->next;
        }
        RandomListNode* head = pHead->next;
        curNode = pHead;
        while(curNode->next!=NULL){
            RandomListNode* pNext = curNode->next;
            curNode->next = pNext->next;
            curNode = pNext;
        }
        return head;
    }
};

发表于 2017-05-06 15:02:13 回复(0)
何恺明的小迷妹头像 何恺明的小迷妹 
//利用C++中的map,虽然空间效率有浪费
//思路简单
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
		if(pHead == NULL) return NULL;
		RandomListNode* p1 =new RandomListNode(pHead->label); 
		RandomListNode* pNewHead = p1;
		RandomListNode* p2 = pHead;
		
		while(p2->next){
			p1->next = new RandomListNode(p2->next->label);
			p2 = p2->next; p1 = p1->next;
		}
        
		map<RandomListNode *, RandomListNode *>  my_Map;  
		my_Map[NULL] = NULL;
		p1 = pNewHead;
		p2 = pHead;
		while(p1 && p2){
			my_Map[p2] = p1;
			p1 = p1->next; p2 = p2->next;
		}
		
		p1 = pNewHead;
		p2= pHead;
		while(p1 && p2){
			p1->random = my_Map[p2->random];
			p1 = p1->next; p2 = p2->next; 
		}
		
		return pNewHead;
    }
};

发表于 2016-08-08 12:57:47 回复(1)
牛客837763号头像 牛客837763号 
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {        
        if(pHead==NULL)	return NULL;
        RandomListNode* current = pHead;
        while(current!=NULL){
            RandomListNode* node = new RandomListNode(current->label);
            node->next  = current->next;
            current->next = node;
            current = node->next;//处理下一个节点
        }
        
        //处理random指针
        current = pHead;
        while(current!=NULL){
            if(current->random!=NULL)
            	current->next->random = current->random->next;
            current = current->next->next;
        }
        
        //生成复制链表
        RandomListNode *temp,*pNewHead;
        pNewHead = pHead->next;
        
        current = pHead;
        temp    = pNewHead;
        while(current!=NULL){
            current->next = current->next->next;
            if(temp->next!=NULL)
                temp->next    = temp->next->next;
            temp = temp->next;
            current = current->next;
        }
        return pNewHead;
    }
};

发表于 2015-09-01 12:03:22 回复(1)
一阶小民头像 一阶小民 
class Solution {
public:
    /*
    	1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
        2、遍历链表，A1->random = A->random->next;
        3、将链表拆分成原链表和复制后的链表
    */
    
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(!pHead) return NULL;
        RandomListNode *currNode = pHead;
        while(currNode){
            RandomListNode *node = new RandomListNode(currNode->label);
            node->next = currNode->next;
            currNode->next = node;
            currNode = node->next;
        }
        currNode = pHead;
        while(currNode){
            RandomListNode *node = currNode->next;
            if(currNode->random){                
            	node->random = currNode->random->next;
            }
            currNode = node->next;
        }
        //拆分
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp;
        currNode = pHead;
        while(currNode->next){
            tmp = currNode->next;
            currNode->next =tmp->next;
            currNode = tmp;
        }
        return pCloneHead;
    }
};

编辑于 2021-03-03 12:02:58 回复(150)
Java
quwhsk头像 quwhsk 
import java.util.*;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        //    使用HashMap记录链表结点，key保存原链表结点，value保存与之对应的新创建的结点
        Map<RandomListNode, RandomListNode> red = new HashMap<>();
        RandomListNode front = pHead;
        while(pHead != null){
            red.put(pHead, new RandomListNode(pHead.label));
            pHead = pHead.next;
        }
        //    然后遍历HashMap的时候就能通过key找到复制的结点，然后串联起来
        for(Map.Entry<RandomListNode, RandomListNode> entry : red.entrySet()){
            entry.getValue().next = red.get(entry.getKey().next);
            entry.getValue().random = red.get(entry.getKey().random);
        }
        
        return red.get(front);
    }
}

发表于 2021-11-21 19:38:05 回复(0)
Python
llfgo4it头像 llfgo4it
思路如上图：沿着旧链表第一遍遍历时，生成值相同的节点，与此同时，如第二步所示，将这些节点的random指针指向旧链表对应节点的random，再将这些节点的random指向新节点。然后第二遍遍历新数组，将这些节点的random指向其random节点的random节点（也就回到了新链表）。

发表于 2020-03-27 21:35:06 回复(0)
Aurora1头像 Aurora1 
 public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null)
			return null;

		RandomListNode t = pHead;
		while (t != null) {
			RandomListNode p = t.next;
			RandomListNode r = new RandomListNode(t.label); // copy next
			t.next = r;
			r.next = p;
			t = p;
		}

		t = pHead;
		RandomListNode r = t.next;
		while (t != null) { 
			if (t.random != null)
				r.random = t.random.next;// copy random
			t = r.next;
			if (t == null) 
				break;
			r = t.next;
		}

		t = pHead;
		r = t.next;
		RandomListNode cHead = r; // copy head
		while (t != null) {
			t.next = r.next;
			t = r.next;
			
			if (t == null) 
				break;
			r.next = t.next;
			r = t.next;
		}
		
		return cHead;
    }

发表于 2016-03-05 16:39:38 回复(1)
JustYoung头像 JustYoung
这道题不能破坏pHead的结构，也就是说，不能返回pHead，即使pHead指向了其它节点
public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null)
			return pHead;
		RandomListNode pNode = pHead;
		while (pNode != null) {
			int val = pNode.label;
			RandomListNode randomListNode = new RandomListNode(val);
			randomListNode.next = pNode.next;
			pNode.next = randomListNode;
			pNode = randomListNode.next;
		}
		pNode = pHead;
		while (pNode != null) {
			RandomListNode next = pNode.next;
			RandomListNode random = pNode.random;
			if (random != null)
				next.random = random.next;
			pNode = next.next;
		}
		pNode = pHead;
		RandomListNode second = pHead.next;
		while (pNode != null) {
			RandomListNode next = pNode.next;
			pNode.next = next.next;
			pNode = next.next;
			if (pNode != null)
				next.next = pNode.next;
		}
		return second;
    }


发表于 2016-03-04 17:24:46 回复(0)
Python
GsOnG头像 GsOnG
直接用深度复制就行
import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        chead=copy.deepcopy(pHead)
        return chead
        # write code here
 
发表于 2018-04-07 16:49:37 回复(7)
Python
李诗水头像 李诗水

最笨的方法实现拷贝，第一遍遍历链表，新建节点并复制next关系，第二遍遍历链表，复制每个节点的random关系，**找到当前节点的**random节点的位置需要从头遍历链表，新建一个新链表指针跟着一起移动，找到random节点后建立当前节点的random关系 

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        tmp = pHead
        newHead = RandomListNode(pHead.label)
        ntmp1 = newHead
        #第一遍遍历存next指针
        while tmp.next:
            ntmp2 = RandomListNode(tmp.next.label)
            ntmp1.next = ntmp2
            ntmp1 = ntmp2
            tmp = tmp.next
        #第二遍遍历存random指针
        tmp, ntmp = pHead, newHead
        while tmp:
            if not tmp.random:
                tmp, ntmp = tmp.next, ntmp.next
                continue
            #每找一个random指针需要从头开始遍历链表，新链表指针跟随一起移动，找到后建立当前节点的random链
            tmp1, ntmp1 = pHead, newHead
            while tmp1:
                if tmp1==tmp.random:
                    break
                tmp1, ntmp1= tmp1.next, ntmp1.next
            ntmp.random = ntmp1
            tmp, ntmp = tmp.next, ntmp.next
        return newHead
另外根据评论中的三步法实现了另一个版本，效率要高得多 
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        #在原链上复制链，在每个节点后插入一个复制节点
        tmp = pHead
        while tmp:
            ntmp = RandomListNode(tmp.label)
            ntmp.next = tmp.next
            tmp.next = ntmp
            tmp = ntmp.next
        #遍历合成链，复制random关系
        tmp = pHead
        while tmp:
            tmp.next.random = tmp.random.next if tmp.random else None
            tmp = tmp.next.next
        #拆链
        tmp,ntmp = pHead,pHead.next
        newHead = pHead.next
        while tmp:
            tmp.next = ntmp.next
            tmp = tmp.next
            if not tmp:
                break
            ntmp.next = tmp.next
            ntmp = ntmp.next
        return newHead

编辑于 2018-09-10 17:27:54 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead == NULL)
            return NULL;
                     unordered_map<RandomListNode*, RandomListNode*> M;
        for(RandomListNode *p=pHead;p!=NULL;p=p->next)
            M[p] = new RandomListNode(p->label);
        
        for(RandomListNode *p=pHead;p!=NULL;p=p->next)
        {
            M[p]->next = M[p->next];
            M[p]->random = M[p->random];
        }
        return M[pHead];
    }
};

发表于 2018-04-03 20:22:41 回复(1)
提交观点

问题信息

链表
难度：
1265条回答 151624浏览

热门推荐

通过挑战的用户

查看代码

相关试题

复杂链表的复制

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号