【leetcode】Copy List with Random Pointer (hard)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路：

做过，先复制一遍指针，再复制random位置，再拆分两个链表。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;// 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) {
if(head == NULL) return NULL; RandomListNode * p = head; //在每个结点后面复制一个自己不管random指针
while(p != NULL)
{
RandomListNode * cpy = new RandomListNode(p->label);
cpy->next = p->next;
p->next = cpy; p = cpy->next;
} //复制random指针
p = head;
while(p != NULL)
{
RandomListNode * cpy = p->next;
if(p->random != NULL)
{
cpy->random = p->random->next;
} p = cpy->next;
} //把原链表与复制链表拆开
RandomListNode * cpyhead = head->next;
p = head;
RandomListNode * cpy = cpyhead;
while(p != NULL)
{
p->next = cpy->next;
cpy->next = (cpy->next == NULL) ? cpy->next : cpy->next->next; p = p->next;
cpy = cpy->next;
} return cpyhead;
}
};int main()
{
RandomListNode * r = new RandomListNode(-);
Solution s;
RandomListNode * ans = s.copyRandomList(r); return ;
}