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.
C Solution:
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* struct RandomListNode *next;
* struct RandomListNode *random;
* };
*/
struct RandomListNode *copyRandomList(struct RandomListNode *head) {
struct RandomListNode *l = head, *r;
while (l) {
r = malloc(sizeof(struct RandomListNode));
r->label = l->label;
r->next = l->next;
l->next = r;
l = r->next;
}
l = head;
while (l) {
l->next->random = l->random ? l->random->next : 0;
l = l->next->next;
}
struct RandomListNode dummy;
r = &dummy;
l = head;
while (l) {
r->next = l->next;
r = r->next;
l->next = l->next->next;
l = l->next;
}
return dummy.next;
}
Python Solution 1:
# 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
p = head
while p:
node = RandomListNode(p.label)
node.next = p.next
p.next = node
p = node.next
p = head
while p:
if p.random:
p.next.random = p.random.next
else:
p.next.random = None
p = p.next.next
res = RandomListNode(0)
p = res
while head:
p.next = head.next
p = p.next
head.next = head.next.next
head = head.next
return res.next
Python Solution 2:
# 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
"""
d = {}
p = head
while p:
d[p] = RandomListNode(p.label)
p = p.next
p = head
while p:
d[p].next = d.get(p.next)
d[p].random = d.get(p.random)
p = p.next
return d.get(head)
Python Solution 3:
# 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
"""
d = {None: None}
p = head
while p:
d[p] = RandomListNode(p.label)
p = p.next
p = head
while p:
d[p].next = d[p.next]
d[p].random = d[p.random]
p = p.next
return d[head]
Python Solution 4:
# 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
"""
d = collections.defaultdict(lambda: RandomListNode(0))
p = head
d[None] = None
while p:
d[p].label = p.label
d[p].next = d[p.next]
d[p].random = d[p.random]
p = p.next
return d[head]
Python Solution 5:
# 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
cur = head
while cur:
copy = RandomListNode(cur.label)
cur.next, copy.next = copy, cur.next
cur = copy.next
cur = head
while cur:
copy = cur.next
copy.random = cur.random.next if cur.random else None
cur = copy.next
_cur = dummy = RandomListNode(0)
cur = head
while cur:
_cur.next = _cur = cur.next
cur.next = cur = cur.next.next
return dummy.next
Summary:
- Could I change the origin list?
- Python Solution 4 is beautiful.
LeetCode: 138. Copy List with Random Pointer
近期评论