LeetCode Entry

138. Copy List with Random Pointer

5.09.2023 medium 2023 kotlin

Copy of a graph

138. Copy List with Random Pointer medium blog post substack

image.png

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
    }