剑指offer - 复杂链表的复制

题目

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

结点的C++定义如下

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

下图是一个含有五个结点的复杂链表，图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling

2.jpeg

分析

思路1

把复制的过程分成两步：

• 第一步是复制原始链表的每个结点，并用m_pNext连接起来；
• 第二步是设置每个结点的m_pSibling指针。

假设原始链表中的某个结点N的m_pSibling指向结点S，由于S在链表中可能在N的前面也可能在N的后面，所以要定位S的位置需要从原始链表的头结点开始找。如果从原始链表的头结点开始沿着m_pNext经过m步找到结点S，那么在复制链表上结点N'的m_pSibling（记为S'）离复制链表的头结点的距离也是沿着m_pSibling指针m步

用这种方法可以为复制链表上的每个结点设置m_pSibling指针。对于一个含有n个结点的链表，由于定位每个m_pSibling都需要从链表头结点开始经过O(n)步才能找到，因此这种方法总的时间复杂度为O(n²)

思路2

上面的时间主要是花在定位m_pSibling上面，可以进行优化。还是分为两步：

• 第一步仍然是复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用m_pNext连接起来。同时把<N,N'>的配对信息放到一个哈希表中；
• 第二步还是设置复制链表上每个结点的m_pSibling。如果在原始链表中结点N的m_pSibling指向结点S，那么在复制链表中，对应的N'应该指向S'。

由于有了哈希表，可以用O(1)的时间根据S找到S'。该方法相当于空间换时间，对于有n个结点的链表，我们需要一个大小为O(n)的哈希表，也就是说我们以O(n)的空间消耗把时间复杂度O(n²)降低到O(n)

思路3

在不用辅助空间的情况下实现O(n)的时间效率

• 第一步仍然是根据原始链表的每个结点N创建对应的N'，把N'连接在N的后面。

34.png

// 复制结点
void CloneNodes(ComplexListNode *pHead) {
    ComplexListNode *pNode = pHead;
    while (pNode != nullptr) {
         // 创建复制结点
        ComplexListNode *pCloned = new ComplexListNode();
        pCloned->m_nValue = pNode->m_nValue;
        pCloned->m_pNext = pNode->m_pNext;
        pCloned->m_pSibling = pNode->m_pSibling;

        pNode->m_pNext = pCloned; // 设置复制结点为当前结点的下一个结点
        pNode = pCloned->m_pNext; // 更新pNode继续进行复制操作
    }
}

• 第二步设置复制出来的结点m_pSibling。

假设原始链表上的N的m_pSibling指向结点S，那么其对应复制出来的N'是N的m_pSibling指向的结点，同样S'也是S的m_pNext指向的结点

20190814132318464_SRGTBM.jpg

// 为复制出来的结点设置m_pSibling
void ConnectSiblingNodes(ComplexListNode *pHead) {
    ComplexListNode *pNode = pHead;
    while (pNode != nullptr) {
        // 获取复制结点
        ComplexListNode *pCloned = pNode->m_pNext;
        if (pNode->m_pSibling != nullptr) {
            pCloned->m_pSibling = pNode->m_pSibling->m_pNext;
        }

        // 下一个结点
        pNode = pCloned->m_pNext;
    }
}

• 第三步把当前长链表拆分为两个链表

奇数位置的结点用m_pNext连接起来就是原始链表，把偶数位置的结点用m_pNext连接起来就是复制出来的链表

参考

《剑指offer》