[数据结构与算法]复制含随机指针的链表

Node类的Next指针和正常链表的Next指针意义一样，而Rand指针时Node新增的指针，可能指向链表的任意节点，也可能指向NULL。

?思路一：HashMap

import java.util.HashMap;
import java.util.Map;

public class LinkCopy {

    static class Node {
        private int number;
        private Node next;
        private Node Rand;

        public Node(int number, Node next, Node rand) {
            this.number = number;
            this.next = next;
            Rand = rand;
        }

        public Node(int number) {
            this.number = number;
        }
    }


    public static void creatArr() {
        LinkCopy.Node node5 = new LinkCopy.Node(1, null, null);
        LinkCopy.Node node4 = new LinkCopy.Node(2, node5, node5);
        LinkCopy.Node node3 = new LinkCopy.Node(3, node4, null);
        LinkCopy.Node node2 = new LinkCopy.Node(3, node3, null);
        LinkCopy.Node node1 = new LinkCopy.Node(2, node2, node3);
        LinkCopy.Node node0 = new LinkCopy.Node(1, node1, null);
        Node node = linkCopy(node0);
        
    }


    public static Node linkCopy(Node node) {

        Map<Node, Node> map = new HashMap();

        Node iter = node;
        while (null != iter) {
            map.put(iter, new LinkCopy.Node(iter.number));
            iter = iter.next;
        }

        iter = node;

        while (null != iter) {

            Node o =  map.get(iter);
            o.next =  map.get(iter.next);
            o.Rand =  map.get(iter.Rand);
            iter = iter.next;
        }
        return map.get(node);

    }
    
}

思路二：让每一个节点的Next是它的复制节点

第一个while循环将复制的节点添加到被复制节点的后面

第二个循环复制随机指针

第三个循环将复制的节点链接成一个链表，第一次循环时returnvalue = returnvalue.next还是指向第一个复制节点。

public class LinkCopy {

    static class Node {
        private int number;
        private Node next;
        private Node Rand;

        public Node(int number, Node next, Node rand) {
            this.number = number;
            this.next = next;
            Rand = rand;
        }

        public Node(int number) {
            this.number = number;
        }
    }


    public static void creatArr() {
        Node node5 = new Node(1, null, null);
        Node node4 = new Node(2, node5, node5);
        Node node3 = new Node(3, node4, null);
        Node node2 = new Node(3, node3, null);
        Node node1 = new Node(2, node2, node3);
        Node node0 = new Node(1, node1, null);
        Node node = copyLink(node0);

        while (null != node) {
            System.out.println(node.number);
            node = node.next;


        }
    }


    public static Node copyLink(Node node) {

        if (null == node) {
            return null;
        }
        Node iter = node;

        while (null != iter) {
            Node copy = new Node(iter.number );
            copy.next = iter.next;
            iter.next = copy;
            iter = copy.next;
        }

        iter = node;
        while (null != iter) {

            if (null != iter.Rand) {
                iter.next.Rand = iter.Rand.next;
            }
            iter = iter.next.next;

        }


        Node returnLink = node.next;
        Node returnvalue = returnLink;
        Node point = null;
        iter = node;
        while (null != iter) {
            point = iter.next;
            iter.next = point.next;
            iter = iter.next;
            returnvalue.next = point;
            returnvalue = returnvalue.next;
        }

        return returnLink;

    }

    public static void main(String[] args) {
        creatArr();
    }
}