首页 > 试题广场 >

拷贝有随机指针的链表

[编程题]拷贝有随机指针的链表
  • 热度指数：37249 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。
请对这个链表进行深拷贝。


说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息
算法知识视频讲解
添加回答
小刀初试头像 小刀初试
做过很多遍了，现在又重写了一遍，代码比较精简。
主要思想还是先拷贝新节点，插入到原节点的后边；然后再 拷贝随机指针；最后将新节点从原链表中分离出，注意要保证原链表正常。 
RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *copy,*p;
        if (!head) return NULL;
        for(p=head;p;p=p->next){
            copy = new RandomListNode(p->label);
            copy->next = p->next;	// insert new at old next
            p = p->next = copy;
        }
        for(p=head;p;p=copy->next){
            copy = p->next;			// copy random point
            copy->random = (p->random?p->random->next:NULL);
        }
        for(p=head,head=copy=p->next;p;){
            p = p->next = copy->next;	// split list
            copy = copy->next = (p?p->next:NULL);
        }
        return head;
    }

发表于 2016-08-04 11:39:34 回复(19)
Ron头像 Ron 
		/*
		 * 每个节点后都插入一个前面节点的拷贝，全部插入后再遍历，改变拷贝的next与random，形成新链表
		 * cur, nex
		 * for node = head : tail : 2
		 * 	cur = node
		 * 	copy = copyOf(cur)
		 * 	cur.next = copy//加入新节点，因此node步长为2
		 * end
		 * for node = head+1 : newTail : 1//next改变了指向，步长为1
		 * 	node.next = node.next.next;
		 * 	node.random = node.random.next;
		 * end
		 * return head.next;
		 */
    public RandomListNode copyRandomList(RandomListNode head) {
		if(head == null || (head.next == null && head.random == null)){
			return head;
		}
		RandomListNode node = head;
		while(node != null){
			RandomListNode copyNode = copyOf(node);
			node.next = copyNode;
			node = node.next.next;
		}
		node = head.next;
		while(node != null){
			if(node.next != null){
				node.next = node.next.next;
			}
			if(node.random != null){
				node.random  = node.random.next;
			}
			node = node.next;
		}

		return head.next;
	}
	private RandomListNode copyOf(RandomListNode node) {
		// TODO Auto-generated method stub
		RandomListNode res = new RandomListNode(node.label);
		res.next = node.next;
		res.random = node.random;
		return res;
	}

编辑于 2016-07-05 12:55:57 回复(5)
C/C++
卷积神经网络哦头像 卷积神经网络哦 
RandomListNode *copyRandomList(RandomListNode *head) { //复制带random指针的链表
    if(!head) return NULL; 

    //先将每一个节点复制一个新节点放在原节点后面 先不管random指针
    RandomListNode *copy, *p;
    for(p = head; p; p = p->next){  
        copy = new RandomListNode(p->label);
        copy->next = p->next;
        p = p->next = copy;
    }


    //为新节点的random指针赋值，若原节点random为NULL 不用管新节点(默认是NULL)
    //若原节点random不为NULL，将新节点的random赋值为原节点random后面的那一个(因为
    //后面这个是复制出来的)

    for(p = head; p ; p = p->next){  
        if(p->random) p->next->random = p->random->next; 
        p = p->next;                                     
    }

    //将新链表从混链表中中提取出来
    copy = p = head->next;
    while(p && p->next && p->next->next)  
        p = p->next = p->next->next;
    return copy;
}
编辑于 2019-04-13 10:57:20 回复(4)
蓝月亮头像 蓝月亮 
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        //第一遍扫描：对每个结点进行复制，把复制出来的新结点插在原结点之后
        RandomListNode node = head;
        while (node != null) {
            RandomListNode newnode = new RandomListNode(node.label);
            newnode.next = node.next;
            node.next = newnode;
            node = newnode.next;
        }
        
        //第二遍扫描：根据原结点的random，给新结点的random赋值
        node = head;
        while (node != null) {
            if (node.random != null) node.next.random = node.random.next;
            node = node.next.next;
        }
        
        RandomListNode newhead = head.next;
        
        //第三遍扫描：把新结点从原链表中拆分出来
        node = head;
        while (node != null) {
            RandomListNode newnode = node.next;
            node.next = newnode.next;
            if (newnode.next != null) newnode.next = newnode.next.next;
            node = node.next;
        }
        
        return newhead;
    }
}

发表于 2017-07-24 17:12:06 回复(3)
顾翅头像 顾翅

先来个怕是要被打的解法：

RandomListNode *copyRandomList(RandomListNode *head) {
  return head;
}

再来个正常解法：

class Solution {
public:

RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == NULL)
        return head;
    RandomListNode* cur = head;
    while (cur != NULL){
        RandomListNode* newNode = new RandomListNode(cur->label);
        newNode->next = cur->next;
        cur->next = newNode;
        cur = newNode->next;
    }
    cur = head;
    while (cur != NULL){
        if (cur->random!=NULL)
            cur->next->random = cur->random->next;
        cur = cur->next->next;
    }
    RandomListNode *cpyHead = head->next;
    cur = head;
    RandomListNode*cpycur = cpyHead;
    while (cur != NULL){
        cur->next = cpycur->next;
        if (cur->next!=NULL)
            cpycur->next = cur->next->next;
        cur = cur->next;
        cpycur = cpycur->next;

    }

    return cpyHead;
}
};
发表于 2018-05-15 21:10:23 回复(2)
W.sl头像 W.sl 
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null){
            return head;
        }
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode oldp = head.next;
        RandomListNode newp=newHead;
        Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
        map.put(newp,head);
        //对旧的链表进行复制
        while(oldp!=null){
            RandomListNode newtemp=new RandomListNode(oldp.label);
            map.put(newtemp,oldp);
            newp.next=newtemp;
            newp=newp.next;
            oldp=oldp.next;
        }
        //对旧链表的random指针进行复制
        oldp=head;
        newp=newHead;
        while(newp!=null){
            newp.random = map.get(newp).random;
            newp=newp.next;
            oldp=oldp.next;
        }
        return newHead;
    }
}

发表于 2016-12-06 16:54:49 回复(2)
已注销头像 已注销 
RandomListNode* copyRandomList(RandomListNode* pHead)
{
	RandomListNode* pNode = pHead;
        if (pHead == NULL)
	    return NULL;
	//1.首先实现random 除外的节点复制,  用map记录新旧节点映射关系
	map<RandomListNode*, RandomListNode*> noMap;
	noMap.insert(pair<RandomListNode*, RandomListNode*>(NULL, NULL));
	RandomListNode* nHead = new RandomListNode(pNode->label);
	noMap.insert(pair<RandomListNode*, RandomListNode*>(pHead, nHead));
	RandomListNode* pNewNode = nHead;

	while (pNode->next!= NULL)
	{
		pNewNode->next = new RandomListNode(pNode->next->label);
		noMap.insert(pair<RandomListNode*, RandomListNode*>(pNode->next, pNewNode->next));
		pNewNode = pNewNode->next;
		pNode = pNode->next;
	}
	//2.调整random指针
	pNewNode = nHead;
	pNode = pHead;
	while (pNewNode != NULL)
	{
		pNewNode->random = noMap.find(pNode->random)->second;
		pNewNode = pNewNode->next;
		pNode = pNode->next;
	}

	return nHead;
}

发表于 2016-03-31 10:30:17 回复(2)
老衲心如止水头像 老衲心如止水 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL)
            return NULL;
        RandomListNode* p = head;
        while(p != NULL)
        {
            RandomListNode* tmp = p->next;
            RandomListNode* newN = new RandomListNode(p->label);
            p->next = newN;
            newN->next = tmp;
            p = tmp;
        }
        p = head;
        while(p != NULL)
        {
            if(p->random != NULL)
                p->next->random = p->random->next;
            p = p->next->next;
        } 
        
        p = head;
        RandomListNode* res = head->next;
        while(p->next != NULL)
        {
            RandomListNode* tmp = p->next;
            p->next = p->next->next;
            p = tmp;
        }
        return res;
        
    }
};

发表于 2017-02-11 21:49:43 回复(0)
小Andy头像 小Andy 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head){
            RandomListNode * newHead = new RandomListNode(head->label);
            newHead->next = copyRandomList(head->next);;
            newHead->random = head->random;
            return newHead;
        }
        return NULL;
    }
};

发表于 2017-10-28 17:32:42 回复(3)
John520101头像 John520101
有bug. 
public RandomListNode copyRandomList(RandomListNode head) {
        return head;
        
    }
 这样都能过。。。。哈哈
发表于 2017-04-17 09:15:40 回复(3)
Spectre_头像 Spectre_ 
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == NULL) return NULL;
        RandomListNode *p = head, *q = NULL;
        while (p) {
            RandomListNode *node = new RandomListNode(p->label);
            node->next = p->next;
            p->next = node;
            p = node->next;
        }
        p = head;
        while (p) {
            q = p->next;
            q->random = p->random == NULL ? NULL : p->random->next;
            p = p->next->next;
        }
        p = head->next;
        while (p) {
            p->next = p->next == NULL ? NULL : p->next->next;
            p = p->next;
        }
        return head->next;
    }
};

发表于 2021-10-06 11:31:47 回复(0)
一朵木兆头像 一朵木兆 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *cur=new RandomListNode(0);
        RandomListNode *p=head;
        RandomListNode *t=cur;
        while(p)
        {
            RandomListNode *tmp=p;
            t->next=new RandomListNode(tmp->label);
            t->next->random=tmp->random;
            t=t->next;
            p=p->next;
        }
        return cur->next;
    }
};

发表于 2020-08-09 11:12:21 回复(2)
牛客477902374号头像 牛客477902374号 
import java.util.*;
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> m = new HashMap<>();
        RandomListNode root1 = head, root2 = null;
        while(root1 != null) {
            RandomListNode copy = new  RandomListNode(root1.label);
            if(root2 != null) root2.next = copy;
            root2 = copy;
            m.put(root1, root2);
            root1 = root1.next;
        }
        root1 = head;
        while(root1 != null) {
            if(root1.random != null) {
                root2 = m.get(root1) ;
                root2.random = m.get(root1.random);
            }
            root1 = root1.next;
        }
        return m.get(head);
    }
}
先复制next，再复制random

发表于 2020-04-16 22:29:41 回复(0)
快到碗里来丫头像 快到碗里来丫
//注意要恢复原链表
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head==nullptr)
            return head;
        RandomListNode *cur=head;
        RandomListNode *tmp=nullptr;
        while(cur!=nullptr){
            tmp=new RandomListNode(cur->label);
            tmp->next=cur->next;
            cur->next=tmp;
            cur=cur->next->next;
        }
        cur=head;
        while(cur!=nullptr){
            cur->next->random=cur->random==nullptr?nullptr:cur->random->next;
            cur=cur->next->next;
        }
        cur=head;
        tmp=cur->next;
        RandomListNode *newhead=tmp;
        while(cur!=nullptr){
            cur->next=tmp->next;
            cur=cur->next;
            tmp->next=cur==nullptr?nullptr:cur->next;
            tmp=tmp->next;
        }
        return newhead;
    }
};

编辑于 2020-04-08 11:25:15 回复(0)
Java
AriesLi头像 AriesLi 
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        /**
         *    首先复制原链表，复制的节点在原链表节点之后，得到 1->1`->2->2`->3->3`...
         *    然后复制随机指针，新链表的随机指针是原链表的下一个节点（例如 1->3 复制为 1`->3`）
         *    将链表拆分为两个链表， 一共遍历三遍，时间复杂度O(n)
         */
        if(head==null){
            return null;
        }
        // 复制链表
        RandomListNode p = head;
        while(p!=null){
            RandomListNode node = new RandomListNode(p.label);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        // 复制随机指针
        p = head;
        RandomListNode q = head.next;
        while(p!=null){
            if(p.random!=null){
                q.random = p.random.next;
            }
            p = q.next;
            if(p!=null) q = p.next;
        }
        // 拆分两个链表
        p = head;
        q = head.next;
        RandomListNode nHead = head.next;
        while(p!=null){
            p.next = q.next;
            p = q.next;
            if(p!=null) {
                q.next = p.next;
                q = p.next;
            };
        }
        return nHead;
    }
}

编辑于 2019-12-31 16:40:33 回复(0)
今天刷了几道题？头像 今天刷了几道题？
还是用递归吧，在leetcode上也是通过了，应该是对了 

class Solution {
public:
    unordered_map<RandomListNode*,RandomListNode*> map;
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head==NULL)
            return NULL;
        if(map.find(head)==map.end()){
            RandomListNode* p=new RandomListNode(head->label);
            map[head]=p;
            p->next=copyRandomList(head->next);
            p->random=copyRandomList(head->random);
        }
        return map[head];
    }
};

发表于 2019-07-08 21:31:38 回复(0)
我没有id头像 我没有id
import java.util.*;
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
      if(head==null){
          return null;
      }
        RandomListNode cur=head;
        RandomListNode next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=new RandomListNode(cur.label);
            cur.next.next=next;
            cur=next;
        }
        cur=head;
        RandomListNode curCopy=null;
        while(cur!=null){
            next=cur.next.next;
            curCopy=cur.next;
            curCopy.random=cur.random!=null?cur.random.next:null;
            cur=next;
        }
        RandomListNode res = head.next;
        cur=head;
        while(cur!=null){
            next=cur.next.next;
            curCopy=cur.next;
            cur.next=next;
            curCopy.next=next!=null?next.next:null;
            cur=next;
        }
        return res;
}
}
发表于 2019-06-24 17:55:03 回复(0)
今天也要乖头像 今天也要乖
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // 先复制next  再复制random
        if(head == nullptr){
            return nullptr;
        }
        RandomListNode *p = nullptr;
        RandomListNode *h = head;
        
        // 复制完了
        while(h!=nullptr){
            p = new RandomListNode(h->label);
            p->next = h->next;
            h->next = p;
            h = p->next;
        }
        // 接下来复制random
        h = head;
        while(h != nullptr){
            if(h ->random == nullptr){
                h->next->random = nullptr;
            }else{
                h->next->random = h->random->next;
            }
            h = h->next->next;
        }
        
        // 接下来取出我的值
        h = head->next;
        RandomListNode *res = h;
        RandomListNode *cur = head;
        while(h!=nullptr){
            cur->next = h->next;
            if(cur->next != nullptr)
                h->next = head->next->next;
            cur = cur->next;
            h = h->next;
        }
        return res;
        
        
        
    }
};
编辑于 2019-05-28 20:51:23 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *copy,*p;
        if(head == NULL)
        	return NULL;
        for(p=head; p; p=p->next)
        {
        	copy = new RandomListNode(p->label);
        	copy->next = p->next;
        	p->next = copy;
        	p = p->next;
		}
		for(p=head; p; p=copy->next)
		{
			copy = p->next;
			copy->random = (p->random?p->random:NULL);
		}
		for(p=head,head=copy=p->next; p; )
		{
			p = p->next = copy->next;
			copy = copy->next = p?p->next:NULL; 
		}
		return head;
    }
};

发表于 2017-08-27 11:26:33 回复(0)
Java
Zfirsty头像 Zfirsty 
//纯递归
import java.util.ArrayList;
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        RandomListNode h = new RandomListNode(head.label);
        f(head,h);
        return h;
    }
    public ArrayList<RandomListNode[]> f(RandomListNode p ,RandomListNode q ){
        if(p==null) return null;
        if(p.next==null) 
            q.next=null;
        else
        	q.next=new RandomListNode(p.next.label);
        q.random = p.random;
        ArrayList<RandomListNode[]> arr = f(p.next,q.next);
        if(arr!=null){
            if(p.random==null) return arr;
            boolean flag = true;
            for(int i=0;i<arr.size();i++){
                if(arr.get(i)[0]==p){
                    arr.get(i)[1].random=q;
                    arr.remove(i);
                    flag=false;
                    break;
                }
            }
            if(flag)
            	arr.add(new RandomListNode[]{p.random,q});
            if(arr.size()==0) return null;
            else return arr;
        }
        if(p.random==null) return null;
       	 ArrayList<RandomListNode[]> list = new ArrayList<RandomListNode[]>();
        list.add(new RandomListNode[]{p.random,q});
        return list;
    }
    
}

发表于 2017-07-19 11:18:48 回复(0)
提交观点

问题信息

链表
难度：
151条回答 26912浏览

热门推荐

通过挑战的用户

相关试题

拷贝有随机指针的链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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