正文
[LeetCode] Copy List with Random Pointe
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目的关键是要让新链表和原有链表发送关联，可以通过这种关联来设置新链表的random pointer
思路：将新链表的元素插入到原有链表元素的后面，如下图所示，就可以根据原有链表的radom->next 就是新链表的random指针
所以分3步骤：
1 新元素插入
2 设置新链表的random
3 拆分大链表，回复old link 和new link
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/ class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) { RandomListNode* pOld = head;
RandomListNode* pNew = NULL;
RandomListNode* pRes = NULL; if(head == NULL) return NULL; // insert every new node after old new node
while(pOld)
{
pNew = new RandomListNode(pOld->label);
if(pOld == head) pRes = pNew;
pNew->next = pOld->next;
pOld->next = pNew;
pOld = pNew->next;
} pOld = head;
// constrct new's random pointer
while(pOld)
{
pNew = pOld->next;
if(pOld->random == NULL)
pNew->random == NULL;
else
pNew->random = pOld->random->next;
pOld = pNew->next;
} // recover old's and new's next pointer
//恢复old list 和new list pOld = head; while(pOld)
{
pNew = pOld->next;
if(pNew == NULL)
pOld->next = NULL;
else
pOld->next = pNew->next;
pOld = pNew;
} return pRes;
}
};
