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)

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

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);
  }
}

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:

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;
  }
}