力扣hot100 随机链表的复制 哈希 深拷贝 通俗易懂

Problem: 138. 随机链表的复制

👩?🏫 参考

💖 哈希表

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

/*
// 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)
	{
		Node cur = head;
		//创建一个哈希表，key是原节点，value是新节点
		Map<Node, Node> map = new HashMap<Node, Node>();
		
		//将原节点和新节点放入哈希表中
		while (cur != null)
		{
			Node node = new Node(cur.val);
			map.put(cur, node);
			cur = cur.next;
		}
		//遍历原链表，设置新节点的next和random
		cur = head;
		while (cur != null)
		{
			Node node = map.get(cur);//node 是新节点
			Node next = map.get(cur.next);// next 是新节点的 next 节点
			Node randonm = map.get(cur.random);// random 是新节点的 random 节点
			node.next = next;
			node.random = randonm;
			cur = cur.next;
		}
//		返回新的头结点
		return map.get(head);
	}
}

💖 拷贝分离法

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        Node p = head;
        //第一步，在每个原节点后面创建一个新节点
        //1->1'->2->2'->3->3'
        while(p!=null) {
            Node newNode = new Node(p.val);
            newNode.next = p.next;
            p.next = newNode;
            p = newNode.next;
        }
        p = head;
        //第二步，设置新节点的随机节点
        while(p!=null) {
            if(p.random!=null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        Node dummy = new Node(-1);
        p = head;
        Node cur = dummy;
        //第三步，将两个链表分离
        while(p!=null) {
            cur.next = p.next;
            cur = cur.next;
            p.next = cur.next;
            p = p.next;
        }
        return dummy.next;
    }
}