leetCode138.Copy List with Random Pointer

题目描述：
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.
大意：给定一个链表，每个节点包含一个random指针，该指针可以指向链表的任意节点或者为空，返回该链表的一个深拷贝

链表结构如上图，其中未画出的指针均指向Null
最容易想到的思路：（很笨很繁琐）
1.遍历链表，创建不包含random引用信息的链表
2.然后再次遍历链表，完善random引用信息

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 * 思路：首先遍历链表，仅仅深拷贝链表节点的label及next值，形成单向链表；然后第二次遍历，深拷贝的链表中每个节点的random引用的指向。
 *
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head ==  null)
            return null;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode temp = head;
        RandomListNode nHead = newHead;
        while(temp.next != null){  //首次遍历，实现简单单向链表的拷贝
            RandomListNode nn = new RandomListNode(temp.next.label);
            nHead.next = nn;
            temp = temp.next;
            nHead = nn;
        }
        temp = head;
        RandomListNode ntemp = newHead;
        while(temp != null){
            RandomListNode tt = head;  //指向原链表 
            RandomListNode ttNew = newHead;  //指向深拷贝的新链表
            if(temp.random != null){  //如果该节点的random不为空
                while(temp.random != tt && tt != null){  //从链表的头节点开始寻找该节点的random引用的指向
                    tt = tt.next;
                    ttNew = ttNew.next;
                }
                //找到random的指向，新链表中标记
                ntemp.random = ttNew;
            }
            temp = temp.next;
            ntemp = ntemp.next;  //新旧链表同步递进
        }
        return newHead;
    }
}

另一种牛B的思路：（来源于网上）
1.首次遍历，在原链表的基础上，复制每个节点，并插入到每个节点之后
2.二次遍历节点，将复制节点的random引用指向原节点的复制节点

3.第三次遍历，实现原节点和复制的节点各自成一链表

public RandomListNode cooyRandomList(RandomListNode head){
    if(head == null)
        return head;
    RandomListNode h = head;
    while(h != null){  //1
        RandomListNode next= h.next;
        h.next = new RandomListNode(h.label);
        h.next.next = next;
        h = next;
    }
    h = head;
    while(h != null){  //2
        if(h.random != null){
            h.next.random = h.random.next;
            h = h.next.next;
        }
    }
    h = head;
    RandomListNode copy = h.next;
    RandomListNode copyHead = copy;
    while(copy.next != null){
        h.next = h.next.next;
        h = h.next;
        copy.next = copy.next.next;
        copy = copy.next;
    }
    h.next = copy.next;
    return copyHead;
}

借助哈希表的思路：
1.遍历链表，将所有的节点及与该节点label值相同的新节点分别作为key和value存入哈希表，其实这一步仅仅拷贝了节点及其label值的信息
2.二次遍历链表，将所有节点的next和random存入哈希表

public RandomListNode cooyRandomList(RandomListNode head){
    if(head == null)
        return head;
    HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
    RandomListNode node = head;
    while(node != null){  //1
        map.put(node,new RandomListNode(node.label));
        node = node.next;
    }
    node = head;
    while(node != null){  //2.遍历链表，为深拷贝的节点的next和random引用赋值
        map.get(node).next = map.get(node.next);   //
        map.get(node).random = map.get(node.random);
        node =  node.next;
    }
}