# Two python solution: iteration and recursion. Both iterate the list once.

• Dfs is the first solution that comes to my mind. Because we can deal with list like a graph
Dfs method can deal the situation with multiple random pointers exsit.
To simply things, you can also use iteration.
Both solutions are listed below.

class Solution(object):
"""
:rtype: RandomListNode
"""
dic = {}
return None
while node != None:
if node.random != None:
if node.random not in dic:
dic[node.random] = RandomListNode(node.random.label)
dic[node].random = dic[node.random]
if node.next != None:
if node.next not in dic:
dic[node.next] = RandomListNode(node.next.label)
dic[node].next = dic[node.next]
node = node.next

class Solution(object):
"""
:rtype: RandomListNode
"""
dic = {}
return None

``````def dfs(self, node, dic):
newNode = RandomListNode(node.label)
dic[node] = newNode
if node.next != None:
if node.next not in dic:
self.dfs(node.next, dic)
newNode.next = dic[node.next]
if node.random != None:
if node.random not in dic:
self.dfs(node.random, dic)
newNode.random = dic[node.random]``````

• ``````class Solution(object):
"""
:rtype: RandomListNode
"""
dic = {}
return None
while node != None:
if node.random != None:
if node.random not in dic:
dic[node.random] = RandomListNode(node.random.label)
dic[node].random = dic[node.random]
if node.next != None:
if node.next not in dic:
dic[node.next] = RandomListNode(node.next.label)
dic[node].next = dic[node.next]
node = node.next
``````
``````class Solution(object):
"""
:rtype: RandomListNode
"""
dic = {}
return None

def dfs(self, node, dic):
newNode = RandomListNode(node.label)
dic[node] = newNode
if node.next != None:
if node.next not in dic:
self.dfs(node.next, dic)
newNode.next = dic[node.next]
if node.random != None:
if node.random not in dic:
self.dfs(node.random, dic)
newNode.random = dic[node.random]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.