LeetCode問題解(88):Copy List with Random Pointer
タイトル:
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. 問題:
2つの方法:O(1)space in place copy、HashTable追加O(n)space copy.
C++作り方一:
C++作り方2:
Javaの作り方1:
Pythonの作り方2:
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. 問題:
2つの方法:O(1)space in place copy、HashTable追加O(n)space copy.
C++作り方一:
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head)
return NULL;
RandomListNode *p = head;
while(p != NULL) {
RandomListNode *newNode = new RandomListNode(p->label);
newNode->next = p->next;
p->next = newNode;
p = p->next->next;
}
p = head;
while(p != NULL) {
if(p->random != NULL)
p->next->random = p->random->next;
p = p->next->next;
}
RandomListNode *newHead = head->next;
p = head;
RandomListNode *q = head->next;
while(p != NULL) {
p->next = q->next;
if(q->next != NULL)
q->next = q->next->next;
p = p->next;
if(p != NULL)
q = p->next;
}
return newHead;
}
};
C++作り方2:
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head)
return NULL;
unordered_map<RandomListNode*, RandomListNode*> nodeToNode;
RandomListNode *p = head;
RandomListNode *newListHead = copyNode(p, nodeToNode);
RandomListNode *q = newListHead;
while(q) {
if(head->random != NULL)
q->random = nodeToNode[head->random];
q = q->next;
head = head->next;
}
return newListHead;
}
RandomListNode* copyNode(RandomListNode* head, unordered_map<RandomListNode*, RandomListNode*> & nodeToNode) {
if(!head)
return NULL;
RandomListNode* newHead = new RandomListNode(head->label);
nodeToNode.insert(pair<RandomListNode*, RandomListNode*>(head, newHead));
newHead->next = copyNode(head->next, nodeToNode);
return newHead;
}
};
Javaの作り方1:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null)
return null;
RandomListNode p = head;
while(p != null) {
RandomListNode newNode = new RandomListNode(p.label);
newNode.next = p.next;
p.next = newNode;
p = p.next.next;
}
p = head;
while(p != null) {
if(p.random != null)
p.next.random = p.random.next;
p = p.next.next;
}
p = head;
RandomListNode newHead = p.next;
while(p != null) {
RandomListNode temp = p.next;
p.next = temp.next;
if(p.next != null)
temp.next = p.next.next;
p = p.next;
}
return newHead;
}
}
Pythonの作り方2:
# Definition for singly-linked list with a random pointer.
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
if head == None:
return None
d = {}
p = head
newHead = self.copyList(p, d)
p = head
q = newHead
while p != None:
if p.random != None:
q.random = d[p.random]
p = p.next
q = q.next
return newHead
def copyList(self, head, d):
if head == None:
return head
newNode = RandomListNode(head.label)
d[head] = newNode
newNode.next = self.copyList(head.next, d)
return newNode