題目描述

• 題目描述：復制一個復雜鏈表，在復雜鏈表中，每個節(jié)點除了有一個next指針指向下一個節(jié)點，還有一個sibling指針指向鏈表中的任意節(jié)點或者null。

解題思路：

1. 原始鏈表為：A(C)->B(E)->C(null)->D(B)->E(null)
2. 復制原始鏈表節(jié)點N，創(chuàng)建N'，并將N'鏈接到N的后邊， 鏈表變?yōu)椋篈(C)->A'(null)>B(E)->B'(null)->C(null)->C'(null)->D(B)->D'(null)->E(null)->E'(null)
3. 設置復制節(jié)點N'的sibling。鏈表變?yōu)椋篈(C)->A'(C')>B(E)->B'(E')->C(null)->C'(null)->D(B)->D'(B')->E(null)->E'(null)
4. 把這個長鏈表拆分為兩個鏈表，獲取拷貝后的鏈表。

代碼

// 節(jié)點結(jié)構(gòu)
class ListNode {
    String value;
    ListNode next;
    ListNode sibling;
    public ListNode(String val) {
        this.value = val;
    }
}

ListNode deepCopy(ListNode root){
    if (root == null) {
        return null;
    }

    // 1. 復制鏈表，插入原始鏈表節(jié)點之后
    ListNode tempNode = root;
    while (tempNode != null) {
        ListNode newNode = new ListNode(tempNode.value);
        newNode.next = tempNode.next;
        tempNode.next = newNode;
        tempNode = newNode.next;
    }

    // 2. 設置sibling
    tempNode = root;
    while (tempNode != null) {
        if (tempNode.sibling!= null) {
            tempNode.next.sibling = tempNode.sibling.next;
        }
        tempNode = tempNode.next.next;
    }

    // 3. 把這個長鏈表拆分為兩個鏈表
    tempNode = root;
    ListNode copyedHead = null;
    ListNode copyedNode = null;

    if (tempNode != null) {
        // 設置復制鏈表的頭節(jié)點
        copyedHead = tempNode.next;
        copyedNode = copyedHead;

        tempNode.next = copyedNode.next;
        tempNode = tempNode.next;
    }
    while (tempNode != null) {
        copyedNode.next = tempNode.next;
        copyedNode = copyedNode.next;

        tempNode.next = copyedNode.next;
        tempNode = tempNode.next;
    }
    return copyedHead;
}