Leetcode[138] Copy List with Random Pointer
10 Nov 2015###Task1 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. ###Python ####O(n) extra space
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return None
dict = {}
itr = head
while itr:
newNode = RandomListNode(itr.label)
dict[itr] = newNode
itr = itr.next
itr = head
while itr:
if itr.next:
dict[itr].next = dict[itr.next]
if itr.random:
dict[itr].random = dict[itr.random]
itr = itr.next
return dict[head]
####No extra space
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return head
self.copyHead(head)
self.copyRandom(head)
return self.split(head)
def copyHead(self, head):
while head:
newNode = RandomListNode(head.label)
temp = head.next
head.next = newNode
newNode.next = temp
head = head.next.next
def copyRandom(self, head):
while head:
if head.random: #check first
head.next.random = head.random.next
head = head.next.next
def split(self, head):
newHead = head.next
while head:
temp = head.next
head.next = temp.next
head = head.next
if temp.next: #check first
temp.next = temp.next.next
return newHead
###Java
/**
* 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 void copyHead(RandomListNode head) {
while (head != null) {
RandomListNode newNode = new RandomListNode(head.label);
newNode.next = head.next;
newNode.random = head.random;
head.next = newNode;
head = head.next.next;
}
}
public void copyRandom(RandomListNode head) {
while (head != null) {
if (head.next.random != null) {
head.next.random = head.random.next;
}
head = head.next.next; // forgot this line !!!!!!!!
}
}
public RandomListNode split(RandomListNode head) {
RandomListNode newHead = head.next;
while (head != null) {
RandomListNode temp = head.next;
head.next = temp.next;
head = head.next;
if (temp.next != null) {
temp.next = temp.next.next;
}
}
return newHead;
}
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
copyHead(head);
copyRandom(head);
return split(head);
}
}
/**
* 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;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode oldHead = head;
while (oldHead != null) {
RandomListNode newNode = new RandomListNode(oldHead.label);
map.put(oldHead, newNode);
oldHead = oldHead.next;
}
oldHead = head;
while (oldHead != null) {
map.get(oldHead).next = map.get(oldHead.next);
map.get(oldHead).random = map.get(oldHead.random);
oldHead = oldHead.next;
}
return map.get(head);
}
}
###Points
- Python needs to check the availability of key before dict[key]
- No extra space in 3 steps: 1. copy every nodes. 2. copy random pointers 3. split into two separate lists
- Needs to check first if head has random pointer before copy !!