首页 > 试题广场 >

复杂链表的复制

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

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

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针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，点此查看相关信息

算法知识视频讲解

Java

gnosed

遍历链表将所有节点保存到一个数组，然后第一次遍历数组，创建新节点先生成正常链表，第二次遍历数组的同时遍历新链表，判断当前节点是否有随机节点（数组和链表顺序对应），根据label值找到指向的随机节点（已经全部创建），时间复杂度O(n^2)，空间复杂度O(n)

    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null){
            return null;
        }
        ArrayList<RandomListNode> list = new ArrayList<>();
        RandomListNode t = pHead;
        while(t!=null){
            list.add(t);
            t=t.next;
        }
        RandomListNode nHead = new RandomListNode(pHead.label);
        t = nHead;
        for(int i =1;i<list.size();i++){
            t.next = new RandomListNode(list.get(i).label);
            t = t.next;
        }
        t = nHead;
        for(int i =0;i<list.size();i++){
            if(list.get(i).random != null){
                int label = list.get(i).random.label;
                for(int j =0;j<list.size();j++){
                    if(list.get(j).label == label){
                        RandomListNode r = new RandomListNode(list.get(j).label);
                        t.random = r;
                        break;
                    }
                }
            }
            t = t.next;
        }
        return nHead;
    }

发表于 2024-11-29 11:49:50 回复(0)

Java

快乐仕忆

这难度标的有问题吗？感觉和简单题目一样。一遍就过了。

编辑于 2023-12-03 12:23:00 回复(0)

Java

不能摆(O∆O)

/*
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) {
        if(pHead == null) return null;
        for (RandomListNode cur = pHead; cur != null; cur = cur.next.next) {
            RandomListNode tmp = cur.next;
            cur.next = new RandomListNode(cur.label);
            cur.next.next = tmp;
        }
        for (RandomListNode cur = pHead; cur != null; cur = cur.next.next) {
            if(cur.random != null) cur.next.random = cur.random.next;
        }
        RandomListNode res = new RandomListNode(0);
        res.next = pHead.next;
        for(RandomListNode cur1 = pHead, cur2 = pHead.next; cur1 != null && cur2!=null;){
            cur1.next = cur1.next.next;
            if(cur2.next != null) cur2.next = cur2.next.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return res.next;
        
    }
}

发表于 2023-04-18 18:23:50 回复(0)

Java

Hadoopdoop

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return null;
        RandomListNode p = pHead;
        HashMap<Integer, Integer> relationMap = new HashMap();
        HashMap<Integer, RandomListNode> addressMap = new HashMap();
        RandomListNode qHead = new RandomListNode(pHead.label);
        RandomListNode q = qHead;
        addressMap.put(q.label, q);
        while (p.next != null) {
            if(p.random != null){
                relationMap.put(p.label, p.random.label);
            }
            RandomListNode nextNode = new RandomListNode(p.next.label);
            addressMap.put(nextNode.label, nextNode);
            q.next = nextNode;
            q = q.next;
            p = p.next;
        }
        if(p.random != null){
            relationMap.put(p.label, p.random.label);
        }
        q = qHead;
        while(q != null){
            if(relationMap.get(q.label) != null) {
                Integer rd = relationMap.get(q.label);
                RandomListNode rnode = addressMap.get(rd);
                q.random = rnode;
            }
            q = q.next;
        }
        return qHead;
    }
}

发表于 2023-03-08 10:18:42 回复(0)

Java

君湖艾

最取巧的通过方式。直接复制头节点后访问。

public class Solution {

public RandomListNode Clone(RandomListNode pHead) {

if(pHead == null )return null;

RandomListNode result = new RandomListNode (pHead.label);

result.next = pHead.next;

result.random = pHead.random;

pHead.next = null;

pHead.random = null;

return result;

}

发表于 2023-03-01 21:32:19 回复(0)

Java

//shuang

import java.util.*;
/*
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) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        for (RandomListNode cur = pHead; cur != null; cur = cur.next) {
            map.put(cur, new RandomListNode(cur.label));
        }
        for (RandomListNode cur = pHead; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(pHead);
    }
}

发表于 2022-09-01 17:39:29 回复(0)

Java

牛客461316693号

遍历链表，遍历时，node指针一直指向头节点，新建指针 temp 对应当前指针，放到map中，一一对应，到尾节点返回，新链表的next和random都在map中一一对应

public class Solution {
private RandomListNode node;
private int i = 0;
private Map<RandomListNode, RandomListNode> nodeList = new HashMap<>();
// private List<Node> nodeList = new ArrayList<>();

public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
re(pHead);
return node;
}

private void re(RandomListNode head) {
if (head == null) {
return;
}
// nodeList.add(head);
if (i == 0) {
node = new RandomListNode(head.label);
nodeList.put(head,node);
i++;
} else {
RandomListNode temp = new RandomListNode(head.label);
nodeList.put(head,temp);
}
re(head.next);
nodeList.get(head).next = nodeList.get(head.next);
nodeList.get(head).random = nodeList.get(head.random);

}

}

发表于 2022-08-17 15:17:42 回复(0)

Java

当鸭只为赎她身

不管怎么变，系统都提示不能引用原链表，真服了

发表于 2022-08-11 16:09:56 回复(1)

Java

新人帅哥

import java.util.*;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode head) {
        if (head == null) return null;
        RandomListNode cur = head;
        while (cur != null) {
            RandomListNode copyNode = new RandomListNode(cur.label);
            copyNode.next = cur.next;
            cur.next = copyNode;
            cur = cur.next.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        RandomListNode copyHead = cur.next, temp = copyHead;
        while (cur != null) {
            if (cur.next != null) {
                cur.next = cur.next.next;
                cur = cur.next;
            }
            if (temp.next != null) {
                temp.next = temp.next.next;
                temp = temp.next;
            }
        }
        return copyHead;
    }
}

发表于 2022-07-23 19:37:12 回复(0)

Java

zaziihohy

    HashMap<RandomListNode, RandomListNode> haved = new HashMap<>();

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead != null) {
            RandomListNode copyNode = new RandomListNode(pHead.label);
            haved.put(pHead, copyNode);
            copyNode.next = Clone(pHead.next);
            copyNode.random = haved.get(pHead.random);
            return copyNode;
        }
        return null;
    }

发表于 2022-06-16 11:12:58 回复(0)

Java

牛客961072936号

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null)
            return null;
        ArrayList<Integer> list =  new ArrayList<>();
        RandomListNode myHead = new  RandomListNode(pHead.label);
        RandomListNode p0 = pHead;
        RandomListNode p2= myHead;
        RandomListNode p1 = pHead.next;
        RandomListNode p3;
        RandomListNode p4;
        while(p0!=null){
            if(p1!=null){
                p2.next = new  RandomListNode(p0.next.label);
                p2 = p2.next;
                p1 = p1.next;
            }
            if(p0.random!=null){
                RandomListNode  p = pHead;
                int j = 0;
                while(p!=null){
                    p = p.next;
                    j++;
                    if(p==p0.random){
                        list.add(j);
                        break;
                    }
                }
            }
            else{
                list.add(-1);
            }
            p0 = p0.next;
                
        }
            p4 = myHead;
            while(p4!=null){
                for(int i=0;i<list.size();i++){
                    int index = list.get(i);
                    p3 = myHead;
                    if(index==-1){
                        p4.random = null;
                    }else{
                        int j = 0;
                        while(p3!=null){
                            p3 = p3.next;
                            j++;
                            if(j==index){
                                p4.random = p3;
                                break;
                            }
                    }
                }
                    p4 = p4.next;
            }      
        }
        return myHead;
    }
}

发表于 2022-06-13 21:30:25 回复(0)

Java

只会暴力做题

维护一个list，两个map：list用于存储顺序遍历链表的元素（这里在遍历的时候就可以顺便维护节点的next节点），map1用于存储每个节点指向的随机节点，map2用于存储每个节点在list中的元素下标，最后遍历map1中的随机指针，将其通过map2映射到list的下标，设置随机指针即可

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        List<RandomListNode> nodeList = new ArrayList<>();
        Map<RandomListNode, RandomListNode> map1 = new HashMap<>();
        Map<RandomListNode, Integer> map2 = new HashMap<>();
        int pst = 0;
        if (pHead == null) {
            return null;
        }
        nodeList.add(new RandomListNode(pHead.label));
        if (pHead.random != null) {
            map1.put(pHead, pHead.random);
        }
        map2.put(pHead, pst++);
        RandomListNode next = pHead.next;
        while (next != null) {
            nodeList.add(new RandomListNode(next.label));
            nodeList.get(nodeList.size() - 2).next = nodeList.get(nodeList.size() - 1);
            if (next.random != null) {
                map1.put(next, next.random);
            }
            map2.put(next, pst++);
            next = next.next;
        }
        if (!map1.isEmpty()) {
            for (Map.Entry<RandomListNode, RandomListNode> entry : map1.entrySet()) {
                nodeList.get(map2.get(entry.getKey())).random = nodeList.get(map2.get(entry.getValue()));
            }
        }
        return nodeList.get(0);
    }
}

发表于 2022-05-18 22:47:39 回复(0)

Java

可能是一只知更鸟

链表拆分法：java代码

public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead==null){
return pHead;
}
RandomListNode cur = pHead;
//将copyNode链接到链表结点的后面
while(cur!=null){
RandomListNode copyNode = new RandomListNode(cur.label);
copyNode.next = cur.next;
cur.next = copyNode;
cur = copyNode.next;
}
//修改随机指针
cur = pHead; //记录原链表结点
RandomListNode pre = pHead.next; //记录复制链表结点
while(cur!=null){
//处理随机结点为null的情况
pre.random = (cur.random==null)?null:cur.random.next;
//判空指针
if(cur.next!=null){
cur = cur.next.next;
}
if(pre.next!=null){
pre = pre.next.next;
}
}
//拆分两个链表使它们分别称为两个独立的链表
cur = pHead;
pre = pHead.next;
RandomListNode ret = pHead.next;
while(cur!=null){
if(cur.next!=null){
cur.next = cur.next.next;
}
if(pre.next!=null){
pre.next = pre.next.next;
}
cur = cur.next;
pre = pre.next;
}
return ret;
}
}

发表于 2022-05-18 15:14:25 回复(0)

Java

哥们给个offer

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

发表于 2022-05-04 10:51:04 回复(0)

Java

zhenggw

import java.util.*;
public class Solution {
    HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return null;
        if(map.containsKey(pHead)) return map.get(pHead);
        RandomListNode newNode = new RandomListNode(pHead.label);
        map.put(pHead,newNode);
        System.out.println(pHead.label + "and" + newNode.label);
        newNode.next = Clone(pHead.next);
        newNode.random = Clone(pHead.random);
        return newNode;
    }
}

发表于 2022-03-24 10:11:48 回复(0)

Java

IF_2000

De了半天最后发现是没有考虑pHead为null的情况，晕。

        public RandomListNode Clone(RandomListNode pHead) {
            RandomListNode head = pHead;
            if(pHead == null) {
                return null;
            }
            while (pHead != null) {
                RandomListNode copy = new RandomListNode(pHead.label);
                copy.next = pHead.next;
                pHead.next = copy;
                pHead = copy.next;
            }//copy node
            pHead = head;
            while (pHead != null){
                RandomListNode copy = pHead.next;//copy不会是null
                if (pHead.random != null) {
                    copy.random = pHead.random.next;
                }
                pHead = copy.next;
            }//copy random
            pHead = head;
            head = pHead.next;

            while (pHead != null){
                RandomListNode copy = pHead.next;//不会是null
                pHead.next = copy.next;
                if (copy.next != null) {
                    copy.next = copy.next.next;
                }
                pHead = pHead.next;
            }
            return head;
        }

发表于 2022-03-14 23:37:43 回复(0)

Java

qxtx265

考虑到一下因素：

1. 因为是深拷贝，所以，空间复杂度最少也是O(n)，即每个节点只创建一次，不重复创建；

2. 因为每个节点有随机指针，所以，如果有一个容器，能把每次遇到的节点给保存起来（未保存过则创建），那在next移动的过程中，发现目标next/random节点已经创键过，就可以直接取出来用，而不用重复创建。自然而然就想到了HashMap。

3. 为了方便从第一个节点开始处理，将一个新的头节点插入到链表起始位置。如果先处理第一个节点的random，则可以少插入这个头结点，省点空间

public RandomListNode Clone(RandomListNode pHead) {
    if (pHead == null) return null;

    HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
    RandomListNode head = new RandomListNode(-1);

    RandomListNode p = head;
    do {
        RandomListNode node;
        if (map.containsKey(pHead)) {
            node = map.get(pHead);
        } else {
            node = new RandomListNode(pHead.label);
            map.put(pHead, node);
        }
        p.next = node;
        p = p.next;

        if (pHead.random != null) {
            if (map.containsKey(pHead.random)) {
                node = map.get(pHead.random);
            } else {
                node = new RandomListNode(pHead.random.label);
                map.put(pHead.random, node);
            }
            p.random = node;
        }
    } while ((pHead = pHead.next) != null);
    return head.next; 
}

发表于 2022-03-03 11:56:16 回复(0)

Java

牛客463257295号

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

RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
//用HashMap得到键值对
//第一个集合存放原节点，编号
HashMap<RandomListNode,Integer> map1 = new HashMap<>();
//第二个集合存放编号，新节点
HashMap<Integer,RandomListNode> map2 = new HashMap<>();
//一个用于记录第几个节点的编号
int i = 1;
//遍历原本的链表，每遍历一个节点，生成两个集合，同时生成新的链表（random都指向空）{
RandomListNode pre = new RandomListNode(0);
RandomListNode temp1 = pHead;
RandomListNode temp2 = pre;
while(true){
if(temp1==null){
break;
}
RandomListNode node = new RandomListNode(temp1.label);
map1.put(temp1,i);
map2.put(i,node);
temp2.next = node;
temp1 = temp1.next;
temp2 = temp2.next;
i++;

}
//再次遍历，先得到原链表中每个节点的random节点的编号，然后让新链表中的节点指向该编号对应的新节点
temp1 = pHead;
temp2 = pre.next;
while(true){
if(temp1 == null){
break;
}
if(temp1.random==null){
temp2.random = null;
}else{
int n = map1.get(temp1.random);
temp2.random = map2.get(n);
}
temp1 = temp1.next;
temp2 = temp2.next;

}
return pre.next;
}
}

发表于 2022-02-25 16:07:02 回复(0)

Java

南寻2020

/*
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) {
        if(pHead == null) return null;
        
        RandomListNode copyNode = new RandomListNode(pHead.label);
        copyNode.next = pHead.next == null ? null : new RandomListNode(pHead.next.label);
        copyNode.random = pHead.random == null ? null : new RandomListNode(pHead.random.label);
        
        RandomListNode cur = copyNode;
        while(pHead.next != null){
            pHead = pHead.next;
            copyNode = copyNode.next;
            copyNode.next = pHead.next == null ? null : new RandomListNode(pHead.next.label);
            copyNode.random = pHead.random == null ? null : new RandomListNode(pHead.random.label);
        }
        return cur;
    }
}

发表于 2022-02-21 15:36:12 回复(0)