random链表的深拷贝

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

 static class Node{
        int val;
        Node next;
        Node random;
        public Node(int val){
            this.val = val;
        }
    }

random 指针是单链表节点结构中新增的指针,random可能指向链表的任意一个节点,也可能指向null.

给定一个Node 节点类型组成的无环链表的节点head ,请实现一个函数 完成这个函数完成这个链表的深拷贝,并返回复制新链表的头结点.

要求时间复制度为O(N) 

空间复制度为O(N)

使用容器

 public static Node copyRandomList(Node head){
        if(head==null){
            return head;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = cur.random!=null ? map.get(cur.random) : null;
            cur = cur.next;
        }
        return map.get(head);
    }

不使用容器(空间复杂度为O(1)):

public static Node copyRandomList(Node head){
        if(head==null){
            return head;
        }
        Node cur = head;
        while(cur!=null){
            Node tem = new Node(cur.val);
            tem.next = cur.next;
            cur.next = tem;
            cur = tem.next;
        }
        cur = head;
        while(cur!=null){
            Node nextNode = cur.next;
            nextNode.random = cur.random != null ? cur.random.next : null;
            cur = nextNode.next;
        }

        cur = head;
        Node tem = head.next;
        Node newhead = cur.next;
        while(cur!=null && tem!=null){
            cur.next = tem!=null ? tem.next : null;
            cur = cur.next;
            tem.next = cur!=null ? cur.next : null;
            tem = tem.next;
        }
        return newhead;
    }

不是使用容器:

在一条链表上复制链表,调整好random 再进行分离.