面试题35：复杂链表的复制

题目：请实现函数一个函数，复制一个复杂链表。在复杂链表中，每个节点除了一个指针指向下一个节点，还有一个指针指向链表的任意一个节点或者null。

图片1

public static Node cloneNodes(Node head) {

if (head ==null)return null;

        Node next = head.mNext;

        Node copy =new Node();

        copy.mValue = head.mValue;

        head.mNext =copy;

        copy.mNext =next;

        if (next !=null)cloneNodes(next);

        return head;

    }

public static void connectSiblingNodes(Node head) {

        int index =0;

        while (head !=null) {

            if (index %2 ==0)if (head.mNext !=null && head.mSibling !=null) head.mNext.mSibling = head.mSibling.mNext;

            head = head.mNext;

            index++;

        }

}

public static Node reconnectNodes(Node head) {

if (head ==null)return null;

        Node result =null,temp =null,workNode = head;

        while (workNode !=null) {

        if (temp ==null) {

                temp =workNode.mNext;

                result =temp;

          } else {

                temp.mNext =workNode.mNext;

                temp =temp.mNext;

            }

            workNode.mNext =workNode.mNext.mNext;

            temp.mNext =null;

            workNode =workNode.mNext;

        }

        return result;

    }

}

class Node {

    String mValue;

    Node mNext;

    Node mSibling;

}