首页 > 试题广场 > 复杂链表的复制
[编程题]复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
示例1

输入


输出


774个回答

添加回答
推荐
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;
    }
};

编辑于 2015-09-22 15:06:12 回复(118)
/*
*解题思路:
*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 回复(45)
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 回复(39)
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 回复(52)
思路:
    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 回复(8)
/*
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 回复(14)
方法一: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两种解法

递归法:

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 回复(18)
因为题目上说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 回复(8)
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 回复(0)
方法一:递归思想
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 回复(10)
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)
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)
//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)
//利用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)
/*
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)

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

解题思路

图4.8 是一个含有5 个结点的复杂链表。图中实线箭头表示next 指针,虚线箭头表示随机引用。为简单起见,指向null 的指针没有画出。

image

image

理解了上面,下面我们就根据这个过程来实现一下。

我的答案

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        //0.判断空的情况
        if(pHead == null){
            return null;
        }

        //1.复制结点
        RandomListNode node = pHead;
        while(node != null){
            //保存下一个结点next-->新建一个克隆结点-->指定node.next到克隆结点
            //-->克隆结点的next指向next结点-->更新node为next结点
            RandomListNode next = node.next;
            RandomListNode cloneNode = new RandomListNode(node.label);
            node.next = cloneNode;
            cloneNode.next = next;
            node = next;
        }

        //2.复制随机引用
        node = pHead;
        while(node != null){
            if(node.random != null){
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }

        //3.分离两个链表
        node = pHead;
        //记录复制的链表的头结点
        RandomListNode newHead = pHead.next;
        while(node != null){
            RandomListNode currNode = node.next;
            //更新原结点的next
            node.next = currNode.next;
            //更新克隆结点的next
            if(currNode.next != null){
                currNode.next = currNode.next.next;
            }
            //更新原结点指针
            node = node.next;
        }

        return newHead;
    }
}
编辑于 2019-03-08 20:31:21 回复(0)
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)
/*
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)
 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)
这道题不能破坏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)