本文共 1378 字，大约阅读时间需要 4 分钟。

一、问题描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

二、代码实现

/*public class RandomListNode {    int label;    RandomListNode next = null;    RandomListNode random = null;    RandomListNode(int label) {        this.label = label;    }}*/public class Solution {    public RandomListNode Clone(RandomListNode pHead) {        if (pHead == null) {            return null;        }                // 1、插入新节点，将副本节点查到原节点的后面（这是第二步的关键）        RandomListNode cur = pHead;        while (cur != null) {            RandomListNode clone = new RandomListNode(cur.label);            clone.next = cur.next;            cur.next = clone;            cur = clone.next;        }                // 2、建立新节点的 random 链接，将副本节点的random指针指向原节点的random指针所指向的节点的下一个节点        cur = pHead;        while (cur != null) {            RandomListNode clone = cur.next;            if (cur.random != null) {                clone.random = cur.random.next;            }            cur = clone.next;        }                // 3、拆分，将所有副本节点分离出来，分成原链表和新链表        //通过不断地让当前节点跟其下一个节点一样指向下下个节点，来使得奇数位置、偶数位置的节点各自连成一个链表        cur = pHead;        RandomListNode pCloneHead = pHead.next;        while (cur.next != null) {            RandomListNode next = cur.next;            cur.next = next.next;            cur = next;        }        return pCloneHead;    }}

转载地址：http://vfnii.baihongyu.com/