链表的深层拷贝，拷贝结点及结点的指向

思考如何深层拷贝一个链表？
1.首先for循坏拷贝就链表的每个结点，然后挂钩，将新旧结点连起来。
2.拷贝旧结点的指向random. for循坏拷贝每个旧节点的指向给新结点。
3。拆开，将新旧链表拆开来，返回新链表的头结点。
再for循坏依次打印结点。

```public class CNode {
int val;
CNode next = null;
CNode random = null;

CNode(int val) {
    this.val = val;
}

public String toString() {
    return String.format("CNode(%d)", val);
}

}

public class Main {
public static void main(String[] args) {
Solution solution = new Solution();//定义一个Solution类的作为接受的变量
testComplexListCopy(solution);

}

/**
 * 1. 构建几组测试数据
 * 2. 进行测试
 * 3. 对测试结果进行打印
 * @return
 */
private static void testComplexListCopy(Solution solution) {
    // 1. 构建测试数据
    CNode head = createComplexList1();
    // 2. 进行测试
    CNode resultHead = solution.copy(head);//solution是Solution类下的变量，自然可以调用Solution类下的方法copy
    // 3. 对测试结果进行打印
    printCList(resultHead);
}

// CNode 必须有一个构造方法，形参是 int val
// 并且，初始化后，next 和 random 都是 null
private static CNode createComplexList1() {
    CNode n1 = new CNode(1);
    CNode n2 = new CNode(2);
    CNode n3 = new CNode(3);
    CNode n4 = new CNode(4);

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

    return n1;
}

// CNode 必须实现一个 String toString() 方法
private static void printCList(CNode head) {
    for (CNode cur = head; cur != null; cur = cur.next) {
        System.out.print(cur + " --> ");
    }
    System.out.println();
}

}

public class Solution {
CNode copy(CNode head) {//copy是Solution类下的方法
if (head == null) {
return null;
}

    CNode p1 = head;
    while (p1 != null) {//新旧挂钩
        CNode p2 = new CNode(p1.val);//拷贝结点

        p2.next = p1.next;
        p1.next = p2;

        p1 = p2.next;
    }

    p1 = head;
    while (p1 != null) {//复制指向   让新的1指向新的2
        CNode p2 = p1.next;
        if (p1.random != null) {
            p2.random = p1.random.next;
        }

        p1 = p2.next;
    }

    p1 = head;
    CNode newHead = head.next;//创造新链表的头结点
    while (p1 != null) {//拆开新旧
        CNode p2 = p1.next;
        p1.next = p2.next;
        if (p2.next != null) {
            p2.next = p2.next.next;
        }

        p1 = p1.next;//相当于更新cur
    }

    return newHead;
}

}