105. 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.

Challenge,

Could you solve it with O(1) space?

Solutions

Solution 1, O(1) space complexity.

Pass the linkedlist two times. Like below.

1->2->3->4

1->1'->2->2'->3->3'->4->4'

Solution 2, Standard O(n) space complexity hashmap solution.

"""
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:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    
    # O(1) space solution
    def copyRandomList(self, head):
        self.copyNext(head)
        self.copyRandom(head)
        return self.split(head)
        
    def copyNext(self, head):
        p = head
        while p:
            nxt = p.next
            p.next = RandomListNode(p.label)
            p.next.next = nxt
            p = nxt
    
    def copyRandom(self, head):
        p = head
        while p:
            if p.random:
                newNode = p.next
                newNode.random = p.random.next
            p = p.next.next
    
    def split(self, head):
        if not head:
            return None
        dummy = RandomListNode(0)
        dummy.next = head.next
        p = dummy.next
        while p and p.next:
            nxt = p.next.next
            head.next = p.next # restore the original
            p.next = nxt
            p = nxt
            head = head.next # restore the original
        return dummy.next

    # Total Runtime: 3221 ms
    # 100% test cases passed.    
    
    
    # hashmap solution
    def copyRandomList(self, head):
        # create object mapping
        hm = dict()
        p = head
        while p:
            hm[p] = RandomListNode(p.label)
            p = p.next
            
        # add links
        p = head
        while p:
            hm.get(p).next = hm.get(p.next)
            hm.get(p).random = hm.get(p.random)
            p = p.next
            
        return hm.get(head)
    
    # # Total Runtime: 3274 ms
    # # 100% test cases passed.