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

思考如何深层拷贝一个链表？
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; }

}