复制带随机指针的链表

题目描述

题目思路

其实最主要是要看懂题目，题目主要是让咱们拷贝这个链表。所以咱们可使用两种方式，一种是牺牲空间的哈希表法，另外一种是不牺牲空间的最优解法。java

哈希表法

简单来讲就是创建一个哈希表，让哈希表的key为老节点，value为相同值的新节点，这样，不管复制random节点仍是next节点均可以经过使用哈希表来完成，具体逻辑以下。
web

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */
class Solution {
    public Node copyRandomList(Node head) {
        //使用哈希表来存储信息,由于要深拷贝，所以须要新的节点（返回的链表中节点所有是新的）
        HashMap<Node,Node>map = new HashMap<>();
        Node curr = head;
        while(curr!=null){
            map.put(curr,new Node(curr.val));
            curr = curr.next;
        }
        //当前哈希表为1->1',2->2',3->3',咱们要返回1'为首的链表
        curr = head;
        while(curr!=null){
            /* 这里更改的都是map中value节点指向的东西，key-value映射关系始终没有改变。 */
            //让1'.next指向(1.next)' ，好比1.next为2，那就让1'.next = 2'
            map.get(curr).next = map.get(curr.next);
            //让1'.random指向（1.random)'，好比1.random为3，那就让1'.random = 3'
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }
}

巧妙算法

一张图就所有将这个算法归纳其中，其中比较巧妙的是复制节点再到置随机指针，简单叙述下，如今每一个节点后面都跟了个相同值的新节点，那么当前旧节点1的random假设指向旧节点3，那么咱们能够直接将旧节点3的next（新节点3）赋值给旧节点1的next（新节点1）的random指针。
具体想不明白代码怎么作能够看下代码，代码逻辑十分清晰。
算法

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
            return null;
        //使用奇妙方法：
        //1.复制相同的节点在当前节点以后
        Node curr = head;
        while(curr!=null){
            Node copy = new Node(curr.val);
            Node xiayige = curr.next;
            curr.next = copy;
            copy.next = xiayige;
            curr = xiayige;
        }
        //2.将新的节点的rand指针链接到正确的新的节点
        curr = head;
        while(curr!=null){
            //这里不用担忧curr.next不存在,由于都是成对成对的
            //可是要防止curr的random指向null
            if(curr.random!=null)
                curr.next.random = curr.random.next;
            curr = curr.next.next;
        }
        //3.将老节点与新节点断开
        Node newhead = head.next;
        curr = head;
        Node res = newhead;
        while(curr!=null){
            curr.next = newhead.next;
            //让1'能指向2'
            //但也要防止到了最后只剩下两个节点，3->3',而此时curr.next已经指向了空
            if(curr.next!=null)
                newhead.next = curr.next.next;
            curr = curr.next;
            newhead = newhead.next;
        }
        return res;
    }
}