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.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

 Method 1. use hashmap, two while loops, first copy all nodes, second link the next and random info

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

        Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

        RandomListNode cur = head;
        while(cur != null) {
            RandomListNode newNode = new RandomListNode(cur.label);
            map.put(cur, newNode);
            cur = cur.next;
        }

        cur = head;

        while(cur != null) {
            if(cur.next != null) map.get(cur).next = map.get(cur.next);
            if(cur.random != null) map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}


Method 2. use hashmap, one while loop, when copy node, copy node info as well as the next and random info

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

        Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

        RandomListNode cur = head;
        while(cur != null) {
            if(!map.containsKey(cur)){
                RandomListNode newNode = new RandomListNode(cur.label);
                map.put(cur, newNode);
            }

            if(cur.next != null && !map.containsKey(cur.next)){
                RandomListNode newNextNode = new RandomListNode(cur.next.label);
                map.put(cur.next, newNextNode);
            }

            if(cur.random != null && !map.containsKey(cur.random)){
                RandomListNode newRandomNode = new RandomListNode(cur.random.label);
                map.put(cur.random, newRandomNode);
            }

            if(cur.next != null) map.get(cur).next = map.get(cur.next);
            if(cur.random != null) map.get(cur).random = map.get(cur.random);

            cur = cur.next;
        }

        return map.get(head);
    }
}


Method 3. no hashmap

public class Solution {
    private void copyList(RandomListNode head) {
        while(head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random; //no need!
            newNode.next = head.next;
            head.next = newNode;

            head = head.next.next;
        }
    }

    private void linkRandom(RandomListNode head) {
        while(head != null) {
            if(head.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while(head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            if(temp.next != null) temp.next = temp.next.next;
            head = head.next;
        }
        return newHead;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        copyList(head);
        linkRandom(head);
        return splitList(head);
    }
}

不同的node class写法后的题

/*
// 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;
    }
};
*/
Method 1. two whiles
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();

        Node currNode = head;
        while (currNode != null) {
            map.put(currNode, new Node(currNode.val, new Node(), new Node()));
            currNode = currNode.next;
        }

        currNode = head;
        while (currNode != null) {
            map.get(currNode).next = map.get(currNode.next);
            map.get(currNode).random = map.get(currNode.random);
            currNode = currNode.next;
        }
        return map.get(head);
    }
}

Method 2. one while
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();

        Node currNode = head;
        while (currNode != null) {
            if (!map.containsKey(currNode)) {
                map.put(currNode, new Node(currNode.val, new Node(), new Node()));
           }
            if (currNode.next != null && !map.containsKey(currNode.next)) {
                map.put(currNode.next, new Node(currNode.next.val, new Node(), new Node()));
            }
            if (currNode.random != null && !map.containsKey(currNode.random)) {
                map.put(currNode.random, new Node(currNode.random.val, new Node(), new Node()));
            }
            map.get(currNode).next = map.get(currNode.next);
            map.get(currNode).random = map.get(currNode.random);
            currNode = currNode.next;
        }
        return map.get(head);
    }
}