# 【LeetCode with Python】 138. 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.

## 代码

# 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:
# @return a RandomListNode
return None
save_list = [ ]
while None != p1:
save_list.append(p1)
p1 = p1.next
copy_second = None
while None != first:
copy_second = RandomListNode(second.label) if None != second else None
copy_first.next = copy_second
copy_first = copy_first.next
first = first.next
if None != second:
second = second.next

while None != p1:
p1_tail = p1.next
p1.next = p2
p2.random = p1
p1 = p1_tail
p2 = p2.next
while None != p2:
p2.random = p2.random.random.next if None != p2.random.random else None
#p1.next = p1.next.next.random if None != p1.next.next else None   # may broken the previous p1.next, so have to save ori list
p2 = p2.next
#p1 = p1.next
len_save_list = len(save_list)
for i in range(0, len_save_list - 1):
save_list[i].next = save_list[i + 1]
save_list[len_save_list - 1].next = None