moonlightshadow123
5/30/2017 - 2:07 PM

138. Copy List with Random Pointer

  1. Copy List with Random Pointer

# 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):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        real2copydict = {None:None}
        dummy = RandomListNode(0)
        p = head
        q = dummy
        while p != None:
            node = RandomListNode(p.label)
            real2copydict[p] = node
            q.next = node
            p = p.next
            q = q.next
        p = head
        q = dummy.next
        while p != None:
            q.random = real2copydict[p.random]
            p = p.next
            q = q.next
        return dummy.next

https://leetcode.com/problems/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.