复杂链表的复制

题目描述

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

分析

1. 复制原节点，将其插入原节点的后面。例如下图：

2. 给每个复制节点的random赋值，如果原节点不为 NULL，则让复制节点指向原节点的random指向的节点的复制节点。即13"要指向7"。

3. 拆分链表：将链表拆分成原链表和复制链表。

代码

<?php
namespace app\index\controller;
// 链表节点结构
class RandomListNode
{
    var $label;
    var $next = NULL;
    var $random = NULL;
    public function __construct($val){
        $this->label = $val;
    }
}

<?php
namespace app\index\controller;

class Test
{
    /**
     * 测试
     */
    public function test()
    {
        // 定义上图所示的链表
        $pHead = new RandomListNode(7);
        $node1 = new RandomListNode(13);
        $node2 = new RandomListNode(11);
        $node3 = new RandomListNode(10);
        $node4 = new RandomListNode(1);

        $pHead->next   = $node1;
        $node1->next   = $node2;
        $node2->next   = $node3;
        $node3->next   = $node4;
        $pHead->random = null;
        $node1->random = $pHead;
        $node2->random = $node4;
        $node3->random = $node2;
        $node4->random = $pHead;

        $clone = $this->MyClone($pHead);  // 调用函数
        print_r($clone);                  // 打印复制的结果
    }

    /**
     * 复制链表
     */
    public function MyClone($pHead)
    {
        $p = $pHead; 
        // 在每一个原节点的后面插入一个新的复制节点。
        while ($p != NULL) {
            $newNode       = new RandomListNode($p->label); // 实例一个新的复制节点
            $newNode->next = $p->next;   // 复制节点的下一个节点指向 $p 的下一个节点
            $p->next       = $newNode;                      // $p 的下一个节点指向复制节点
            $p             = $newNode->next;                // 指针节点移到下一个原节点
        }

        $p = $pHead;  // 重新指向链表头
        // 给每个复制节点的随机指针 $random 赋值
        while ($p != NULL) {
            $newNode = $p->next;  // 原节点的下一节点是它的复制节点
            // 如果原节点X有随机指针指向Y，则X的复制节点X`的随机指针指向Y的复制节点Y`。
            if ($p->random != NULL) $newNode->random = $p->random->next;
            $p = $newNode->next;  // 移到下一个原节点
        }

        $p         = $pHead;
        $cloneHead = $cloneNode = $p->next;  // 复制节点链表的链表头
        // 将链表拆分成：原节点链表、复制节点链表
        while ($p != NULL) {
            $cloneNode = $p->next;          // 移到复制节点
            $p->next   = $cloneNode->next;  // 移到下一个原节点
            $p         = $p->next;
        }

        return $cloneHead;
    ｝
}