Mapping old nodes to new ones

When you must copy a structure whose links point anywhere, build the nodes first and the links second.

Why it works

Nodes first, links second

Pass one: walk the original and create a copy of every node, storing a map from each original node to its copy. Set no links at all.

Pass two: walk the original again. For each original node, look up its copy, and set that copy's links by looking up the copies of whatever the original pointed at.

By the second pass every copy exists, so no lookup can fail and no ordering question arises. The awkwardness disappears entirely.

Below is pass one only, ending with the check that makes pass two trivial: every node any link could possibly point at is already a key in the map.

1class Node:2    def __init__(self, val):3        self.val = val4        self.next = None5        self.jump = None            # points at any node, or None6 7first, second = Node(1), Node(2)8first.next = second9first.jump = second10second.jump = first                  # points backward11 12copies = {}13node = first14while node:15    copies[node] = Node(node.val)    # pass one: nodes only, no links at all16    node = node.next17 18print("originals in the map:", [original.val for original in copies])19print("fresh copies made:   ", [copy.val for copy in copies.values()])20print("both link targets already present:", first in copies, second in copies)

Nothing points anywhere yet. That is the point: pass two can look up any target and find it.

Predict the output· 5 min

Predict the output: setting links during the first pass

This tries to do it in one pass, creating each copy and wiring its jump link immediately. Type the two values it prints, separated by a single space.

Python

1class Node:2    def __init__(self, val):3        self.val, self.next, self.jump = val, None, None4 5first, second = Node(1), Node(2)6first.next = second7first.jump = second                  # forward8second.jump = first                  # backward9 10copies = {}11node = first12while node:13    copies[node] = Node(node.val)14    copies[node].jump = copies.get(node.jump)15    node = node.next16 17print(copies[first].jump, copies[second].jump.val)

Printed output

Problem· 25 min

Copy List With Random Pointer

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val):3 self.val = val4 self.next = None5 self.jump = None # points at any node, or None6 7first, second = Node(1), Node(2)8first.next = second9first.jump = second10second.jump = first # points backward11 12copies = {}13node = first14while node:15 copies[node] = Node(node.val) # pass one: nodes only, no links at all16 node = node.next17 18print("originals in the map:", [original.val for original in copies])19print("fresh copies made: ", [copy.val for copy in copies.values()])20print("both link targets already present:", first in copies, second in copies)

1class Node:2 def __init__(self, val):3 self.val, self.next, self.jump = val, None, None4 5first, second = Node(1), Node(2)6first.next = second7first.jump = second # forward8second.jump = first # backward9 10copies = {}11node = first12while node:13 copies[node] = Node(node.val)14 copies[node].jump = copies.get(node.jump)15 node = node.next16 17print(copies[first].jump, copies[second].jump.val)