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

Amazon session

  • Method 1: dfs + hashMap 
    /*
// 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) {
        this.map = new HashMap<>();
        return dfs(head);
    }
    private Node dfs(Node node){
        if(node == null) return null;
        Node cur = new Node();
        cur.val = node.val;
        map.put(cur.val, cur);
        cur.next = dfs(node.next);
        cur.random = node.random != null ? map.get(node.random.val): null;
        return cur;
    }
}