鏈表的深層拷貝，拷貝結點及結點的指向

思考如何深層拷貝一個鏈表？
1.首先for循壞拷貝就鏈表的每個結點，然后掛鉤，將新舊結點連起來。
2.拷貝舊結點的指向random. for循壞拷貝每個舊節(jié)點的指向給新結點。
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;//創(chuàng)造新鏈表的頭結點
    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;
}

}