# Leetcode: Copy List with Random Pointer

Copy List with Random Pointer

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Basic Ideas:
##            |------------|
##            |            v
##            1  --> 2 --> 3 --> 4
##
##            |--------------------------|
##            |                          v
##            1  --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
##                   |                         |
##                   |-------------------------|
## Complexity: Time O(n), Space O(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):
"""
:rtype: RandomListNode
"""
return None

## duplicate the list
while p:
newNode = RandomListNode(p.label)
newNode.next = p.next
p.next = newNode
p = newNode.next

## copy the randome pointer
##   odd node is the original list
##   even node is the new list
while p1:
p2 = p1.next
if p1.random:
p2.random = p1.random.next
# move to next
p1 = p1.next.next

# change back the pointers