讨论/《链表》 - 复制带随机指针的链表/
《链表》 - 复制带随机指针的链表
共 7 个回复

第一次循环HashMap的key存开始的链表的每个节点,先不管next指针和random指针(不管就是默认为null)。value存new出来新的节点,再循环一次,因为hashmap中已经有每个所有节点该对应的新链表的节点了。再根据hashmap.get(p.next)和hashmap.get(p.random)来得到新的链表应该的新的节点都是哪些。

public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head, q;
        while(p != null){
            q = new Node(p.val);
            map.put(p, q);
            p = p.next;
        }
        p = head;
        q = map.get(p);
        while(p != null){
            q.next = map.get(p.next);
            q.random = map.get(p.random);
            q = q.next;
            p = p.next;
        }
        return map.get(head);
    }
4
public class Solution {
    private Map<Node, Node> visited = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node oldNode = head;
        Node newNode = new Node(oldNode.val);
        visited.put(oldNode, newNode);
        while (oldNode != null) {
            newNode.random = getClonedNode(oldNode.random);
            newNode.next = getClonedNode(oldNode.next);
            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return visited.get(head);
    }

    private Node getClonedNode(Node oldNode) {
        if (oldNode != null) {
            if (!visited.containsKey(oldNode)) {
                visited.put(oldNode, new Node(oldNode.val));
            }
            return visited.get(oldNode);
        }
        return null;
    }
}
2

使用哈希表 [key:原来的节点 value:新复制节点]

重点下面两行:
1.取当前节点的复制节点的next指向当前节点next的复制节点
map.get(cur).next = map.get(cur.next);
2.取当前节点的复制节点的random指向当前节点random的复制节点
map.get(cur).random = map.get(cur.random);

class Solution {
    public Node copyRandomList(Node head) {
        //使用哈希表
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //1.存储复制的新节点 key:原来的节点 value:新复制节点
        while(cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //2.将新复制节点的next和random进行复制链接
        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);
    }
}
1

解题思路

利用一个哈希表,将原始链表的节点指针作为键,深拷贝得到的新节点作为值,两次遍历即可实现赋值带随机指针的链表。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
private:
public:
    Node* copyRandomList(Node* head) {
        if (!head)  return nullptr;
        unordered_map<Node*, Node*> mem = {};
        mem.insert(make_pair(nullptr, nullptr));
        Node* sentinel = new Node(0);   //哨兵节点
        Node* cur = head;
        while (cur) {
            sentinel->next = new Node(cur->val);
            mem.insert(make_pair(cur, sentinel->next));
            sentinel = sentinel->next;
            cur = cur->next;
        }
        cur = head;
        sentinel = mem[cur];
        while (cur) {
            sentinel->random = mem[cur->random];
            cur = cur->next;
            sentinel = sentinel->next;
        }

        return mem[head];
    }
};
1
//自己写的不用hashmap的解法,也是两次循环,不知为什么第12个case错了
public Node copyRandomList(Node head) {
        Node copyHead = new Node(10001);
        Node copyCur = copyHead;
        Node cur = head;
//第一次循环先构造链表,但不考虑random
        while (cur != null) {
            copyCur.next = new Node(cur.val);
            cur = cur.next;
            copyCur = copyCur.next;
        }
//构造random指向的位置
        cur = head;
        copyCur = copyHead.next;
        while (cur != null) {
            Node cursor = copyHead.next;
           if (cur.random != null) {
                while (cursor.val != cur.random.val) cursor = cursor.next;
                copyCur.random = cursor;
            }
            copyCur = copyCur.next;
            cur = cur.next;
        }
        return copyHead.next;
    }

哈希。。。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)
            return head;
        map<Node*, int> index;
        vector<Node*> newNodes;
        Node* tmp = head;
        int i = 0;
        while(tmp){
            index[tmp] = i;
            Node* newNode = new Node(tmp->val);
            newNodes.push_back(newNode);
            if(i > 0){
                newNodes[i-1]->next = newNode;
            }
            i++;
            tmp = tmp->next;
        }
        tmp = head;
        int j = 0;
        while(tmp){
            if(tmp->random){
               int ind =  index[tmp->random];
               newNodes[j]->random = newNodes[ind];
            }
            tmp = tmp->next;
            j++;
        }
        return newNodes[0];
    }
};

Java 常规

class Solution {
    Map<Node,Node> map=new HashMap<>();
    public Node copyRandomList(Node head) {
        dfs(head);
        return map.get(head);
    }
    void dfs(Node root){
        if(root==null||map.containsKey(root))return;
        Node node=new Node(root.val);
        map.put(root, node);
        dfs(root.next);
        dfs(root.random);
        node.next=map.get(root.next);
        node.random=map.get(root.random);
    }
}