《剑指offer第二版》面试题35：复杂链表的复制（java）

题目描述

• 题目描述：复制一个复杂链表，在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个sibling指针指向链表中的任意节点或者null。

解题思路：

1. 原始链表为：A(C)->B(E)->C(null)->D(B)->E(null)
2. 复制原始链表节点N，创建N'，并将N'链接到N的后边， 链表变为：A(C)->A'(null)>B(E)->B'(null)->C(null)->C'(null)->D(B)->D'(null)->E(null)->E'(null)
3. 设置复制节点N'的sibling。链表变为：A(C)->A'(C')>B(E)->B'(E')->C(null)->C'(null)->D(B)->D'(B')->E(null)->E'(null)
4. 把这个长链表拆分为两个链表，获取拷贝后的链表。

代码

// 节点结构
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. 复制链表，插入原始链表节点之后
    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) {
        // 设置复制链表的头节点
        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;
}