LC-138 复制带随机指针的链表

原题链接

讨论澄清

这道题仍然是一道链表题，因此任然可用用链表的思想来加以解答。但是这道题可以借助更巧妙的方法：HashMap来进行思路简化。本题需要清洗的理解题目的意思，理解什么是深拷贝。

思路简述

这里简述用HashMap来解题的思路：首先hashMap是一个key-value映射表，因此我们可以把要复制的目标节点放在key位置，复制后的节点放在对应的value位置。并且需要进行两次循环，第一次循环现将目标节点对应的值复制到value上，next和random的指向先不设置，均指向null。第二次循环再对next和random进行设置。循环的终止条件均是被复制的节点为空

注意事项

本题中的节点其实仔细分析可以发现和普通的节点有很大相似之处，只是相比普通节点只有next，本题中的链表的节点还有random，因此我们需要的就是给每一个random也要进行拷贝。

具体代码

方法一：利用hashmap

   public Node copyRandomList(Node head) {
   //  可以看出此链表的节点不同于一般节点 里面多了一个random
               if(head==null) return null;
        //用map把对应节点全部复制一份
        Map<Node,Node> map = new HashMap<>();
        //第一个循环先把值复制出来,next和random先指向空
            Node cur= head;
            while(cur!=null){
                map.put(cur,new Node(cur.val,null,null));
                cur = cur.next;
            }
            //第二个循环用来设置next和random
            cur = head;
            while(cur!=null){
                //拿到key节点的next和random赋值给value节点
                map.get(cur).next  = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
    }

方法二：利用链表知识

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    // 复制节点，紧挨到到后面
    // 1->2->3  ==>  1->1'->2->2'->3->3'
    Node cur = head;
    while (cur != null) {
        Node cloneNode = new Node(cur.val);
        cloneNode.next = cur.next;
        Node temp = cur.next;
        cur.next = cloneNode;
        cur = temp;
    }
    // 处理random指针
    cur = head;
    while (cur != null) {
        if (cur.random != null) {
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }
    // 分离两个链表
    cur = head;
    Node cloneHead = cur.next;
    while (cur != null && cur.next != null) {
        Node temp = cur.next;
        cur.next = cur.next.next;
        cur = temp;
    }
    // 原始链表头：head 1->2->3
    // 克隆的链表头：cloneHead 1'->2'->3'
    return cloneHead;
}