# 138.Copy-List-with-Random-Pointer

## 138. Copy List with Random Pointer

## 题目地址

<https://www.lintcode.com/problem/copy-list-with-random-pointer/>

<https://leetcode.com/problems/copy-list-with-random-pointer/>

## 题目描述

```
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.
```

## 代码

### Approach #1 Recursive

**Complexity Analysis**

* Time Complexity: O(N)
* Space Complexity: O(N)

```java
class Node {
  public int val;
  public Node next;
  public Node random;

  public Node() {}
  public Node(int _val, Node _next, Node _random) {
    val = _val;
    next = _next;
    random = _random;
  }
}

class Solution {
  HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

  public Node copyRandomList(Node head) {
    if (head == null) return null;

    if (this.visitedHash.containsKey(head)) {
      return this.visitedHash.get(head);
    }

    Node node = new Node(head.val, null, null);

    this.visitedHash.put(head, node);

    node.next = this.copyRandomList(head.next);
    node.random = this.copyRandomList(head.random);

    return node;
  }
}
```

### Approach #2 Iterative with O(N) Space

```java
class Solution {
  HashMap<Node, Node> visited = new HashMap<Node, Node>();
  public Node getClonedNode(Node node) {
    if (node != null) {
      if (this.visited.containsKey(node)) {
        return this.visited.get(node);
      } else {
        this.visited.put(node, new Node(node.val, null, null));
        return this.visited.get(node);
      }
    }
    return null;
  }

  public Node copyRandomList(Node head) {
    if (head == null) return null;

    Node oldNode = head;

    Node newNode = new Node(oldNode.val);
    this.visited.put(oldNode, newNode);

    while (oldNode != null) {
      newNode.random = this.getCloneNode(oldNode.random);
      newNode.next = this.getClonedNode(oldNode.next);

      oldNode = oldNode.next;
      newNode = newNode.next;
    }

    return this.visited.get(head);
  }
}
```

```java
class RandomListNode {
  int val;
  RnadomListNode next, random;
  RnadomListNode(int x) {this.val = x;}
}

public class Solution {
    public RnadomListNode copyRandomList(RandomListNode head) {
    if (head == null) return null;

    RandomListNode dummy = new RandomListNode(0);
    RandomListNode curNode = dummy;
    HashMap<RandomListNode, RandomListNode> randomMap = 
      new HashMap<RandomListNode, RandomListNode>();
    while (head != null) {
      RandomListNode newNode = new RandomListNode(head.val);
      curNode.next = newNode;
      randomMap.put(head, newNode);
      newNode.random = head.random;

      head = head.next;
      curNode = curNode.next;
    }

    curNode = dummy.next;
    while (curNode != null) {
      if (curNode.random != null) {
        curNode.random = randomMap.get(curNode.random);
      }
      curNode = curNode.next;
    }

    return dummy.next;
  }
}
```

// Solution 2:

```java
public class Solution {
    public RandomListNode copyRandomList(RnadomListNode head) {
    RandomListNode dummy = new RandomListNode(0);
    RandomListNode curNode = dummy;
    HashMap<RandomListNode, RandomListNode> hash_map =
      new HashMap<RandomListNode, RandomListNode>();
    while (head != null){
      RandomListNode newNode = null;
      if (hash_map.containsKey(head)){
        newNode = hash_map.get(head);
      } else {
        newNode = new RandomListNode(head.val);
        hash_map.put(head, newNode);
      }
      curNode.next = newNode;

      if (head.random != null) {
        if (hash_map.containsKey(head.random)) {
          newNode.random = hash_map.get(head.random);
        } else {
          newNome.random = new RandomListNode(head.random.val);
          hash_map.put(head.random, newNode.random);
        }
      }

      head = head.next;
      curNode = curNode.next;
    }

    return dummy.next;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/linked-list/138.copy-list-with-random-pointer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.