https://leetcode.com/problems/copy-list-with-random-pointer

First, we can go through the linked list, put all nodes to hash table and then connect all additional nodes. It takes additional O(n) memory. If we more memory efficient solution, we need to think more.

Unfortunately, we can not use BFS or DFS here, because, we do not really know the number of node for random field, only the reference, which can be found in either O(n) or we need to keep all references in hash table.

The trick to solve this problem in O(1) memory is to use duplication trick. Imagine, that we have list 7 -> 13 -> 11 -> null, then we need to do 3 stages:

  1. Create duplicated list, that is 7 -> 7 -> 13 -> 13 -> 11 -> 11 -> null, where every second value will be elements of new list.
  2. Second step is to add random field pointers, it can be done as curr.next.random = curr.random.next, that is where we need to point random pointer of second node with value 7? We need to look at random field of first 7 and take next element. We need to be careful with null pointers.
  3. Finally, we need to cut list into two parts, we can do it with simple 2 pointers curr and nxt, which always will have adjacent elements inside.

Complexity: time complexity is O(n), this is complexity of every stage. Space complexity is O(1), if we do not count our output list.

The trick to solve is to duplicate our list, after each node add the node with the same value, then add new random fields, and then cut it into 2 lists.

class Solution:
    def copyRandomList(self, head):
        dummy = Node(-1)
        dummy.next = head
        curr = head
        while curr:
            tmp = Node(curr.val)
            tmp.next = curr.next
            curr.next = tmp
            curr = tmp.next
            
        curr = head
        while curr:
            curr.next.random = curr.random.next if curr.random else None
            curr = curr.next.next
            
        curr, nxt = dummy, head
        while nxt:
            curr.next = nxt.next
            curr = nxt
            nxt = curr.next
            
        return dummy.next

If you like the solution, you can upvote it on leetcode discussion section: Problem 0138