# LeetCode 138Copy List with Random Pointer

## LeetCode 138 Copy List with Random Pointer Problem

``````# 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):
#     """
#     :rtype: RandomListNode
#     """
#     # hash O(n) and O(n)
#     dic = collections.defaultdict(lambda: RandomListNode(0))
#     dic[None] = None
#     while n:
#         dic[n].label = n.label
#         dic[n].next = dic[n.next]
#         dic[n].random = dic[n.random]
#         n = n.next

#     # hash O(n) and O(n)
#     dic = {}
#     dic[None] = None
#     while p is not None:
#         q.next = RandomListNode(p.label)
#         dic[p] = q.next
#         p = p.next
#         q = q.next
#     while p is not None:
#         q.next.random = dic[p.random]
#         p = p.next
#         q = q.next

# Modify original structure: Original->Copy->Original->Copy
# node.next.random = node.random.next
# O(n) and O(1)
while p is not None:
next = p.next
copy = RandomListNode(p.label)
p.next = copy
copy.next =  next
p = next
while p is not None:
if p.random is not None:
p.next.random = p.random.next
p = p.next.next
if p is not None:
else:
while p is not None:
copy = p.next
p.next = copy.next
p = p.next
if p is not None:
copy.next = p.next