# Copy List with Random Pointer Solutions in Python

Number 138

Difficulty Medium

Acceptance 36.6%

Link LeetCode

Other languages C++

## Solutions

### Python solution by haoel/leetcode

# method 1: using a dict and store each node as key, each copied node as value# Space complexity: O(n)# Time complexity: O(n)def copyRandomList(self, head):d = {}m = n = headwhile m:d[m] = RandomListNode(m.label)m = m.nextwhile n:d[n].next = d.get(n.next)d[n].random = d.get(n.random)n = n.nextreturn d.get(head)# Method 2:# Space complexity: O(1)# Time complexity: O(n)def copyRandomList(self, head):if not head: return None# Step 1: copy each node and link them together with original onescurr = headwhile curr:new = RandomListNode(curr.label)new.next = curr.nextcurr.next = newcurr = curr.next.next# Step 2: build random node for each copied nodescurr = headwhile curr:if curr.random: curr.next.random = curr.random.nextcurr = curr.next.next# Step 3: restore the original list and extract copied listnewhead = head.nextpold = headpnew = newheadwhile pnew.next:pold.next = pnew.nextpold = pold.nextpnew.next = pold.nextpnew = pnew.nextpold.next = Nonepnew.next = Nonereturn newhead