复杂链表的复制
程序员文章站
2022-06-11 20:16:28
...
复杂链表中每个节点不仅有指向下一个节点的next指针,还具有一个random指针指向任一个节点或者为空。
复制复杂链表的关键是复制好指针的指向问题,最能想到的思路就是先将链表的next进行复制之后,再根据每一个节点的random指针的指向再去原链表中去找对应的节点,这种思路是可以的,但是每访问一个节点都要去找random指向的节点时间复杂度为O(n2);
如果用一个哈希表将每个节点的random指向进行映射,查找的时候不就很方便,但是这种方案会额外开辟空间,以空间换时间,时间复杂度为O(n);
那么有没有方法在原来的链表上就可以完成复制呢?
首先可以将复杂链表中的每一个节点的next指针先进行赋复制,并连接到对应的节点的后面
void CloneList(ListNode* phead)
{
if (phead == NULL)
{
return;
}
ListNode* plist = phead;
while (plist)
{
ListNode* newNode = new ListNode(plist->_val);
newNode->_next = plist->_next;
newNode->_random = NULL;
plist->_next = newNode;
plist = newNode->_next;
}
}
再将源节点的random指针进行复制
void Copy_random(ListNode* phead)
{
ListNode* plist = phead;
while (plist != NULL)
{
ListNode* clone = plist->_next;
if (plist->_random != NULL)
{
clone->_random = plist->_random->_next;
}
plist = clone->_next;
}
}
最后将长链表进行分离
ListNode* SplitList(ListNode* phead)
{
ListNode* plist = phead;
ListNode* pNode = NULL;
ListNode* cloneNode = NULL;
//先确定链表的头部
if (plist != NULL)
{
pNode = cloneNode = plist->_next;
plist->_next = cloneNode->_next;
plist = plist->_next;
}
while (plist)
{
cloneNode->_next = plist->_next;
cloneNode = cloneNode->_next;
plist->_next = cloneNode->_next;
plist = plist->_next;
}
return pNode;
}
上一篇: Smarty3.1.8 有关问题
下一篇: 复杂链表的复制