美文网首页
剑指offer 面试题26:复杂链表的复制

剑指offer 面试题26:复杂链表的复制

作者: qmss | 来源:发表于2016-06-11 17:51 被阅读0次

题目:

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

请实现函数complexListNode* clone(complexListNode* pHead),复制一个复杂链表。在复杂链表中,每个结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任意结点或者NULL.

解法一:
先不管m_pSibling指针,将链表当做一个单链表复制,然后再遍历原链表,依次复制m_pSibling指针。但由于寻找新链表m_pSibling指针指向的结点需要遍历,因此时间复杂度为O(n^2)

解法二:
解法一的时间复杂度主要耗费在m_pSibling复制过程中需要遍历,而避免遍历的方法之一就是hash表,因此可以考虑建立一个原结点N和新结点N'的映射关系,这样在复制m_pSibling的时候,在新链表中寻找结点时直接查表即可。

解法三:
寻找时空效率更高的解法。
第一步:复制链表,只是这个时候的复制,是把新的结点复制到原结点的后面,即N1->N1'->N2->N2',这样m_pSibling指向的结点在新链表中也就是原结点的m_pNext结点
第二步:将第一步得到的链表拆分即可。

相关文章

网友评论

      本文标题:剑指offer 面试题26:复杂链表的复制

      本文链接:https://www.haomeiwen.com/subject/oaqedttx.html