[数据结构与算法]java实现复制带随机指针的链表（力扣138题）

我们要复制以上链表的。重点要保证映射关系的一致

public class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution{
    public Node copyRandomList(Node head) {
        Node cur = head;
        Node newNode = null;

        //将新结点插入到对应老结点的后面
        while (cur!=null){
            newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = cur.next.next;
        }

        cur = head;
        //复制random的映射关系
        while (cur!=null){
            //由于之前将新结点插入到了对应老结点后
            //通过找到老结点的random即可找到新结点random指向的结点即为老结点的random的next
            if (cur.random == null){
                cur.next.random = null;
            }else{
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //拆开老结点和新结点
        cur = head;
        Node newHead = head.next;
        while (cur!=null){
            newNode = cur.next;
            // 改变 cur.next 和 newNode.next
            cur.next = cur.next.next;   // newNode.next
            if (newNode.next != null) {
                newNode.next = newNode.next.next;
            }

            // 让 cur 还指向下一个老结点
            cur = cur.next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        Node head = new Node(7);
        Node n1 = new Node(13);
        Node n2 = new Node(11);
        Node n3 = new Node(10);
        Node n4 = new Node(1);

        head.next = n1;
        head.random = null;
        n1.next = n2;
        n1.random = head;
        n2.next = n3;
        n2.random = n4;
        n3.next = n4;
        n3.random = n2;
        n4.next = null;
        n4.random = head;

        Node node = new Solution().copyRandomList(head);
    }

}

?

这样，我们就完成了深拷贝。?

?