leetCode-138:Copy List with Random Pointer

问题描述

给定一个链表，链表的节点中有个随机指针，指向链表中的任何一个节点，或者指向空。要求将这个链表进行深度拷贝。题目链接：**点我**

样例输入输出

无

问题解法

用一个 map 存储原先老节点和新节点的对应关系，第一次循环遍历链表，复制链表的 next 指针指向的内容，同时将新老节点的映射关系进行存储。第二次循环遍历链表，根据原先链表节点的随机指针指向的节从 map 中取出对应的新节点，并将当前遍历到的新节点的随机指针指向这个新的随机节点，从而完成链表随机指针的复制。代码如下

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution
{
    public Node copyRandomList(Node head)
    {
        if (head == null)
        {
            return null;
        }
        
        Map<Node, Node> map = new HashMap<>();
        Node newHead = new Node(head.val);
        map.put(head, newHead);
        Node p = head.next;
        Node current = newHead;
        while (p != null)
        {
            Node pNew = new Node(p.val);
            current.next = pNew;
            map.put(p, pNew);
            p = p.next;
            current = current.next;
        }
        
        p = head;
        while (p != null)
        {
            Node pNew = map.get(p);
            pNew.random = map.get(p.random);
            p = p.next;
        }
        
        return newHead;
    }
}