138. Copy List with Random Pointer.md

138. Copy List with Random Pointer

Question:

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.

Thinking:

• Method1:

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode cur = head;
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode dummyCur = dummy;
        Map<Integer, RandomListNode> m = new HashMap<>();
        while(cur != null){
            dummyCur.next = new RandomListNode(cur.label);
            m.put(cur.label, dummyCur.next);
            dummyCur = dummyCur.next;
            cur = cur.next;
        }
        dummyCur.next = null;
        cur = head;
        dummyCur = dummy.next;
        while(cur != null){
            if(cur.random == null)
                dummyCur.random = null;
            else
                dummyCur.random = m.get(cur.random.label);
            dummyCur = dummyCur.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

二刷

1. 通过map，键是原来的结点，值是复制出来的新的结点。通过查找哈希表，我们判断当前的结点是否已经被生成。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        RandomListNode result = new RandomListNode(0);
        Map<RandomListNode, RandomListNode> m = new HashMap<>();
        RandomListNode cur = head;
        RandomListNode curRes = result;
        while(cur != null){
            RandomListNode copy = null;
            if(m.containsKey(cur))
                copy = m.get(cur);
            else{
                copy = new RandomListNode(cur.label);
                m.put(cur, copy);
            }
            curRes.next = copy;
            curRes = curRes.next;
            if(cur.random != null){
                if(!m.containsKey(cur.random)){
                    copy.random = new RandomListNode(cur.random.label);
                    m.put(cur.random, copy.random);
                }else
                    copy.random = m.get(cur.random);
            }
            cur = cur.next;
        }
        return result.next;
    }
}

2. 通过label作为键，而不是原结点对象。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        RandomListNode result = new RandomListNode(0);
        Map<Integer, RandomListNode> m = new HashMap<>();
        RandomListNode cur = head;
        RandomListNode curRes = result;
        while(cur != null){
            RandomListNode copy = null;
            if(m.containsKey(cur.label))
                copy = m.get(cur.label);
            else{
                copy = new RandomListNode(cur.label);
                m.put(cur.label, copy);
            }
            curRes.next = copy;
            curRes = curRes.next;
            if(cur.random != null){
                if(!m.containsKey(cur.random.label)){
                    copy.random = new RandomListNode(cur.random.label);
                    m.put(cur.random.label, copy.random);
                }else
                    copy.random = m.get(cur.random.label);
            }
            cur = cur.next;
        }
        return result.next;
    }
}

Third Time

• Method 1: dfs + map
  • This question is a graph question, for each nodes, we can consider its next and random as two neighbours.
  • Related question 133. Clone Graph

  /*
  // Definition for a Node.
  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 {
      private Map<Integer, Node> map;
      public Node copyRandomList(Node head) {
          map = new HashMap<>();
          return head == null ? null: dfs(head, head.val);
      }
      private Node dfs(Node node, int num){
          if(node == null) return null;
          else if(map.containsKey(num)) return map.get(num);
          else{
              Node cur = new Node();
              cur.val = num;
              map.put(num, cur);
              cur.next = node.next == null ? null: dfs(node.next, node.next.val);
              cur.random = node.random == null ? null: dfs(node.random, node.random.val);
              return cur;
          }
      }
  }