Copy List with Random Pointer leetcode

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.

第一种方法：用hashmap

1. 把新链表和原链表按照key: value存入hashmap， 并给每个新链表附上next指针

2. 按顺序读取hashp存储的旧链表， 然后把random指针复制给新链表（必须放在hashmap读取是因为直接读取random指针就无法按顺序）

一共扫面了两次链表 时间复杂度O(n) 空间复杂度O(n)

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null){ 
            return null;
        }
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode newhead = new RandomListNode(head.label);
        map.put(head, newhead);
        RandomListNode node = head.next;
        RandomListNode pre = newhead;
        while (node != null){
            RandomListNode tem = new RandomListNode(node.label);
            map.put(node, tem);
            pre.next = tem;
            pre = pre.next;
            node = node.next;
        }
        node = head;
        pre = newhead;
        while (node != null){
            pre.random = map.get(node.random);
            pre = pre.next;
            node = node.next;
        }
        return newhead;
        
    }
}

第二种方法：

深度拷贝一个链表

第一步：复制链表并插入原链表原链表（1->2->3->4）新链表(1->1'->2->2'->3->3'->4->4')

第二步： 改变新链表的random指针

第三步：分离连个链表
三次线性扫描，所以时间复杂度是O(n)。空间复杂度是O(1)。

public class Solution {

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        RandomListNode node = head;
        while (node != null) {
            RandomListNode tem = new RandomListNode(node.label);
            tem.next = node.next;
            node.next = tem;
            node = node.next.next;
        }
        node = head;
        while (node != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        node = head;
        RandomListNode newhead = head.next;
        while(node != null){
            RandomListNode tem = node.next;
            node.next = tem.next;
            if (tem.next != null) {
                tem.next = tem.next.next;
            }
            node = node.next;
        }
        return newhead;
    }
}