首页 > 试题广场 > 复杂链表的复制

[编程题]复杂链表的复制

热度指数：705324 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息

算法知识视频讲解

Java

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 回复(100)

Python

Yannyezixin

思路：

1. 把复制的结点链接在原始链表的每一对应结点后面

2. 把复制的结点的random指针指向被复制结点的random指针的下一个结点

3. 拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，next指针要重新赋值None(判定程序会认定你没有完成复制）

# -*- 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):
        if not pHead:
            return None
        
        dummy = pHead
        
        # first step, N' to N next
        while dummy:
            dummynext = dummy.next
            copynode = RandomListNode(dummy.label)
            copynode.next = dummynext
            dummy.next = copynode
            dummy = dummynext
        
        dummy = pHead
        
        # second step, random' to random'
        while dummy:
            dummyrandom = dummy.random
            copynode = dummy.next
            if dummyrandom:
            	copynode.random = dummyrandom.next
            dummy = copynode.next
        
        # third step, split linked list
        dummy = pHead
        copyHead = pHead.next
        while dummy:
            copyNode = dummy.next
            dummynext = copyNode.next
            dummy.next = dummynext
            if dummynext:
                copyNode.next = dummynext.next
            else:
                copyNode.next = None
            dummy = dummynext

        return copyHead

发表于 2016-07-26 07:27:31 回复(22)

老石基

public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null)
            return null;
        RandomListNode pCur = pHead;
        //复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
        while(pCur!=null){
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;
            pCur = node.next;
        }
        pCur = pHead;
        //复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
        while(pCur!=null){
            if(pCur.random!=null)
            	pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        RandomListNode head = pHead.next;
        RandomListNode cur = head;
        pCur = pHead;
        //拆分链表
        while(pCur!=null){
            pCur.next = pCur.next.next;
            if(cur.next!=null)
                cur.next = cur.next.next;
            cur = cur.next;
            pCur = pCur.next;
        }
		return head;        
    }
}

编辑于 2016-04-16 12:18:40 回复(46)

C/C++

搁浅的鱼儿

1、递归法

/*
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* pClonedHead=new RandomListNode(pHead->label);
        pClonedHead->next = pHead->next;
        pClonedHead->random = pHead->random;
        
        //递归其他节点
        pClonedHead->next=Clone(pHead->next);
        
        return pClonedHead;
    }
};

2、三步法

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    //复制原始链表的任一节点N并创建新节点N'，再把N'链接到N的后边
    void CloneNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=NULL)
        {
            RandomListNode* pCloned=new RandomListNode(0);
            pCloned->label=pNode->label;
            pCloned->next=pNode->next;
            pCloned->random=NULL;
             
            pNode->next=pCloned;
             
            pNode=pCloned->next;
        }
    }
    //如果原始链表上的节点N的random指向S，则对应的复制节点N'的random指向S的下一个节点S'
    void ConnectRandomNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=NULL)
        {
            RandomListNode* pCloned=pNode->next;
            if(pNode->random!=NULL)
                pCloned->random=pNode->random->next;
            pNode=pCloned->next;
        }
    }
    //把得到的链表拆成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表
    RandomListNode* ReConnectNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        RandomListNode* pClonedHead=NULL;
        RandomListNode* pClonedNode=NULL;
         
        //初始化
        if(pNode!=NULL)
        {
            pClonedHead=pClonedNode=pNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
             
        }
        //循环
        while(pNode!=NULL)
        {
            pClonedNode->next=pNode->next;
            pClonedNode=pClonedNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
        }
         
        return pClonedHead;
         
    }
    //三步合一
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectRandomNodes(pHead);
        return ReConnectNodes(pHead);
    }
};

3、哈希表法

这个算法写了好久才调出来，指针操作真的很难呀！思想很简单，但是操作起来不简单！！！为方便读者，解析要详细!!!

空间时间复杂度均是O（n）

/*
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;
        
        //定义一个哈希表
        unordered_multimap<RandomListNode*,RandomListNode*> table;
        
        // 开辟一个头结点
        RandomListNode* pClonedHead=new RandomListNode(pHead->label);
        pClonedHead->next=NULL;
        pClonedHead->random=NULL;
        
        // 将头结点放入map中
        table.insert(make_pair(pHead,pClonedHead));
        
        //设置操作指针
 		RandomListNode* pNode=pHead->next;
        RandomListNode* pClonedNode=pClonedHead;
        
        // 第一遍先将简单链表复制一下
        while(pNode!=NULL)
        {
            // 不断开辟pNode的拷贝结点
            RandomListNode* pClonedTail=new RandomListNode(pNode->label);
            pClonedTail->next=NULL;
        	pClonedTail->random=NULL;
            
            //连接新节点，更新当前节点
            pClonedNode->next=pClonedTail;
            pClonedNode=pClonedTail;
            
            //将对应关系  插入到哈希表中
            table.insert(make_pair(pNode,pClonedTail));
            
            //向后移动操作节点
            pNode=pNode->next;
        }
        
        //需从头开始设置random节点，设置操作指针
        pNode=pHead;
        pClonedNode=pClonedHead;
		
        // 根据map中保存的数据，找到对应的节点
        while(pNode!=NULL)
        {
            
            if(pNode->random!=NULL)
            {
                //找到对应节点，更新复制链表
                pClonedNode->random=table.find(pNode->random)->second;
            }
            
            //向后移动操作节点
            pNode=pNode->next;
            pClonedNode=pClonedNode->next;
        }
        
        return pClonedHead;
        
    }
};

编辑于 2016-07-24 00:22:07 回复(56)

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

方法一：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)

打工不可能打工的

JAVA使用哈希表，时间复杂度O(N)，额外空间复杂度O(N)

import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = pHead;
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            cur = cur.next;
        }
        RandomListNode resHead = map.get(pHead);
        cur = pHead;
        while (cur != null) {
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return resHead;
    }
}

编辑于 2018-07-10 18:39:23 回复(5)

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)

因为题目上说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)

一阶小民

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

江南消夏

方法一：递归思想

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)

大闲人柴毛毛

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)

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)

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

/*
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号

/*
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)

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

这道题不能破坏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

直接用深度复制就行

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)