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.


Could you solve it with O(1) space?


Solution 1, O(1) space complexity.

Pass the linkedlist two times. Like below.



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):
        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.