Loading...
Loading...
Loading...
A study group keeps its notes as a linked list. Each note links to the next note, and may also have a see-also link to any note in the list, or to none. Before an exam, the group wants a backup: a completely separate copy, where each copied note links only to copied notes. The starter code builds the list. Make the copy using only the links of the original. To show that the copy is separate, set every value in the original list to 0 after copying. Then print the copy.
Example 1
Input
4 7 13 11 10 -1 0 3 2
Output
7 13 11 10 -1 7 10 11
Note 13 points to note 7, note 11 points to 10 and note 10 points to 11. The original is set to 0, but the copy still shows the real values.
Example 2
Input
3 5 6 7 2 2 2
Output
5 6 7 7 7 7
Every note points to the last note, 7.
Try the problem first. Open one hint at a time.
A copied see-also link must point to the copy of the target note, not to the original note.
Walk the list once and make a copy of every node. Store each pair in a HashMap<Node, Node> from original node to its copy.
Walk the list a second time. Now every copy exists, so set copy.next = map.get(old.next) and copy.random = map.get(old.random).
There is also a way with O(1) extra space: put each copy right after its original, set the see-also links, then split the two lists apart.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor