题目:
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结点
第二步:将第一步得到的链表拆分即可。