题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：
因为新链表也需要复制旧链表的random指针，而random指向的节点也有其next和random，需要保持链表的连贯，所以需要考虑先做出一条新链表，再去构建每一个节点的random节点，而如何同步random节点就是问题所在。有两种解决办法。
解法一：构建同一链表后拆分
1.新旧链表构建在一起，形成Z字型
2.为每一个新节点同步random节点
3.分开两个链表
class Solution
{
public:
RandomListNode *Clone(RandomListNode *
pHead)
{
if (pHead ==
NULL)
return NULL;
RandomListNode *newHead =
new RandomListNode(pHead->
label);
RandomListNode *curNode1 =
pHead;
RandomListNode *curNode2 =
newHead;
// 新旧链表形成Z链
while (curNode1)
{
curNode2->next = curNode1->
next;
curNode1->next =
curNode2;
curNode1 = curNode2->
next;
curNode2 = curNode1 == NULL ? NULL :
new RandomListNode(curNode1->
label);
}
curNode1 =
pHead;
curNode2 =
newHead;
// 新链添加random
while (curNode1)
{
curNode2->random = curNode1->random == NULL ? NULL : curNode1->random->
next;
curNode1 = curNode2->
next;
curNode2 = curNode1 == NULL ? NULL : curNode1->
next;
}
curNode1 =
pHead;
curNode2 =
newHead;
// 脱链
while (curNode1)
{
curNode1->next = curNode2->
next;
curNode2->next = curNode1->next == NULL ? NULL : curNode1->next->
next;
curNode1 = curNode1->
next;
curNode2 = curNode2->
next;
}
return newHead;
}
};
解法二：利用哈希表
先构建新链表（label,next），同时哈希表存储（旧链表节点，新链表节点）映射关系
再遍历一遍旧链表，利用哈希的映射为新链表random赋值，oldNode->random = hash[newNode->random]
class Solution
{
public:
RandomListNode *Clone(RandomListNode *
pHead)
{
if (pHead ==
NULL)
return NULL;
map<RandomListNode *, RandomListNode *>
m;
RandomListNode *curNode1 =
pHead;
RandomListNode *curNode2 =
new RandomListNode(curNode1->
label);
RandomListNode *newHead =
curNode2;
m[curNode1] =
curNode2;
while (curNode1)
{
curNode2->next = curNode1->next == NULL ? NULL :
new RandomListNode(curNode1->next->
label);
curNode1 = curNode1->
next;
curNode2 = curNode2->
next;
m[curNode1] =
curNode2;
}
curNode1 =
pHead;
curNode2 =
newHead;
while (curNode1)
{
curNode2->random = m[curNode1->
random];
curNode1 = curNode1->
next;
curNode2 = curNode2->
next;
}
return newHead;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10075817.html
