克隆链表

一种特殊的单链表节点类描述如下：

class Node { 
	int value; 
	Node next; 
	Node rand; 
	Node(int val) {
    value = val;
  } 
}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。

要求：给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

package copy;

import java.util.HashMap;

public class CopyListWithRandom {
    /**
     * 链表复制
     * <p>使用Hash表实现</p>
     * <p>时间复杂度：O(n)</p>
     * <p>额外空间复杂度：O(n)</p>
     *
     * @param root head
     *
     * @return 复制的链表
     */
    public static Node copyListWithRand1(Node root) {
        // 特殊值判断
        if (root == null) {
            return null;
        }
        // 定义Hash表，构造老节点与新节点的对应关系
        HashMap<Node, Node> map = new HashMap<>();
        Node old = root;
        while (old != null) {
            map.put(old, new Node(old.value));
            old = old.next;
        }
        // 构造复制的节点的链表关系
        old = root;
        while (old != null) {
            map.get(old).next = map.get(old.next);
            map.get(old).rand = map.get(old.rand);
            old = old.next;
        }
        return map.get(root);
    }

    /**
     * 链表复制
     * <p>不用Hash链表构造新老节点对应关系</p>
     * <p>将新节点始终放在老节点的next来构造对应关系</p>
     * <p>时间复杂度：O(n)</p>
     * <p>额外空间复杂度：O(1)</p>
     *
     * @param root head
     *
     * @return 复制的链表
     */
    public static Node copyListWithRand2(Node root) {
        // 特殊值判断
        if (root == null) {
            return null;
        }
        // 新建新节点，构造新老节点对应关系
        Node next;
        Node old = root;
        while (old != null) {
            next = old.next;
            Node node = new Node(old.value);
            node.next = next;
            old.next = node;
            old = next;
        }
        // 复制老节点的rand关系
        old = root;
        while (old != null) {
            old.next.rand = old.rand == null ? null : old.rand.next;
            old = old.next.next;
        }
        // 分离新老链表
        old = root;
        Node head = old.next;
        while (old != null) {
            next = old.next;
            old.next = next.next;
            old = old.next;
            next.next = old == null ? null : old.next;
        }
        return head;
    }

    public static class Node {
        public int value;
        public Node next;
        /**
         * rand指针是单链表节点结构中新增的指针
         * rand可能指向链表中的任意一个节点
         * 也可能指向null
         */
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
    }
}