《剑指Offer》-35.复杂链表的复制

题干

请实现函数 ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个节点除了有一个 m_pNext 指针指向下一个节点，还有一个 m_pSlibing 指针指向链表中任意节点或者 nullptr。节点的 C++ 定义如下：

struct ComplexListNode{
    int m_nValue;
    ComplexListNode* m_pNext;
    ComplexListNode* m_pSlibing;
}

解题思路

思路一

先复制链表的Next指针，然后复制Sibling指针，由于复制Sibling指针时需要定位位置，所以时间复杂度是O(n^2)。

思路二

使用空间换时间的思路，先复制链表的Next指针，过程中将原节点和复制节点保存到一个哈希表中，当复制Sibling指针时，可以通过查找哈希表来定位节点位置，所以时间复杂度是O(n)，由于需要一个大小为n的哈希表，所以空间复杂度也是O(n)。

思路三

复制链表的Next指针，过程中将复制节点连接在原节点之后，当复制Sibling指针时，可以通过原节点的Sibling指向的下一节点来确定复制节点的Sibling节点，这样就完成来复制，然后再将链表拆成两个就完成来复制。

代码实现

<?php

class ListNode
{
    private $val;
    private $next;
    private $sibling;

    public function __get($name)
    {
        return $this->$name;
    }

    public function __set($name, $value)
    {
        $this->$name = $value;
    }
}

function getList()
{
    $node1 = new ListNode();
    $node1->val = 'A';

    $node2 = new ListNode();
    $node2->val = 'B';

    $node3 = new ListNode();
    $node3->val = 'C';

    $node4 = new ListNode();
    $node4->val = 'D';

    $node5 = new ListNode();
    $node5->val = 'E';

    $node1->next = $node2;
    $node1->sibling = $node3;

    $node2->next = $node3;
    $node2->sibling = $node5;

    $node3->next = $node4;
    $node3->sibling = null;

    $node4->next = $node5;
    $node4->sibling = $node2;

    $node5->next = null;
    $node5->sibling = null;

    return $node1;
}

function cloneList($head)
{
    cloneNext($head);
    cloneSibling($head);
    $cloneList = splitList($head);
//    printList($head);
//    printList($cloneList);
}

function cloneNext(&$head)
{
    $node = $head;
    while ($node != null) {
        $cloneNode = new ListNode();
        $cloneNode->val = $node->val;
        $cloneNode->next = $node->next;
        $cloneNode->sibling = null;

        $node->next = $cloneNode;
        $node = $cloneNode->next;
    }
}

function cloneSibling(&$head)
{
    $node = $head;
    while ($node != null) {
        $clone = $node->next;
        if ($node->sibling != null) {
            $clone->sibling = $node->sibling->next;
        }
        $node = $clone->next;
    }
}

function splitList(&$head)
{
    $node = $head;
    $cloneHead = null;
    $cloneNode = null;
    if ($node != null) {
        $cloneHead = $cloneNode = $node->next;
        $node->next = $cloneNode->next;
        $node = $node->next;
    }

    while ($node != null) {
        $cloneNode->next = $node->next;
        $cloneNode = $cloneNode->next;
        $node->next = $cloneNode->next;
        $node = $node->next;
    }

    return $cloneHead;
}

function printList($head)
{
    $node = $head;
    while ($node != null) {
        echo $node->val.' ';
        if ($node->sibling != null) {
            echo $node->sibling->val.' ';
        }
        $node = $node->next;
    }
}

$head = getList();
cloneList($head);