题解 | #复杂链表的复制#

题目：复杂链表的复制
描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分，3，5，#，2，#分别的表示为
1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null
如下图:

思路：在原节点后面插入相同的节点，原节点的next指向新节点

遍历复制的节点

拆分链表

Java代码如下所示：

public class Solution{
    /**
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead)
    {
        RandomListNode oldNode=pHead;
        if(pHead==null){
            return null;
        }
        //复制每个节点并插入到原节点后面
        while(oldNode!=null){
            RandomListNode newNode=new RandomListNode(oldNode.label); 
//生成一个新节点，和原节点一样
            newNode.next=oldNode.next; 
//将newNode插入原节点和他的next节点之间
            oldNode.next=newNode;
            oldNode=oldNode.next.next; //指向下一个原节点
        }

              //将新节点的随机节点设好
        oldNode=pHead;
        while(oldNode!=null){
            RandomListNode newNode=oldNode.next; 
//oldnode的next节点就是复制的原节点
            if(oldNode.random!=null){
                newNode.random=oldNode.random.next; 
//原节点的复制的新节点的random指向的随机节点
            }
            oldNode=newNode.next;
        }

             //将原来的链表进行拆分
        oldNode=pHead;
        RandomListNode copyHead=oldNode.next;
        while(oldNode!=null){
            RandomListNode copyNode=oldNode.next; //指向复制出来的第一个节点
            oldNode.next=copyNode.next; //指向原节点的原来的next节点
            if(copyNode.next!=null){
                copyNode.next=copyNode.next.next; //更新复制节点的next
            }
            oldNode=oldNode.next; //更新原节点的next

        }
        return copyHead;

    }
}

时间复杂度：需要遍历节点，时间复杂度为0(N)。