# 5.09.2023 [138. Copy List with Random Pointer]

Copy of a graph

5.09.2023

138. Copy List with Random Pointer medium
blog post

Problem TLDR

Copy of a graph

Intuition

Simple way is just store mapping old -> new.
The trick from hint is to store new nodes in between the old ones, then mapping became old -> new.next & new -> old.next.

Approach

One iteration to make new nodes, second to assign random field and final to split lists back.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(1)

Code

    fun copyRandomList(node: Node?): Node? {
      var curr = node
      while (curr != null) {
        val next = curr.next
        curr.next = Node(curr.`val`).apply { this.next = next }
        curr = next
      }
      curr = node
      while (curr != null) {
        curr.next?.random = curr.random?.next
        curr = curr.next?.next
      }
      curr = node
      val head = node?.next
      while (curr != null) {
        val currNew = curr.next
        val nextOrig = currNew?.next
        val nextNew = nextOrig?.next
        curr.next = nextOrig
        currNew?.next = nextNew
        curr = nextOrig
      }
      return head
    }