Problem overview
The method copyRandomList receives the head of a singly linked list whose ListNodes have a val, a next link and a random link. The random link points to any node of the list or is nil. The method must return a deep copy: n brand-new nodes with the same values, whose next and random links point only to other new nodes, in the same pattern as the original. For an empty list it returns nil.
Here the statement asks for O(n) time and O(1) extra space, so a dictionary from originals to copies, which would take O(n) space, is not allowed. The original list must also be the same when the method ends, since the caller still owns it.
In the first example, the nodes written as [val, random_index] are [7,null], [13,0], [11,4], [10,2] and [1,0], and the copy has the same values and the same random positions.
Approach: let each copy sit next to its original
A dictionary answers one question: "which node is the copy of this one?" The lesson answers it without extra memory by putting each copy directly after its original in the list. Then the copy of any node X is simply X.next. The method makes three passes:
- Interleave. Turn
A → B → CintoA → A' → B → B' → C → C', where each primed node is a copy that holds only the value. - Set the random links. If an original
XhasX.random = Y, then the copyX', which isX.next, getsY.next, which isY'. No map is needed. - Split. Separate the two lists again: restore every original's
nextand link the copies to each other.
The interleaved list is temporary. It uses the original nodes' next fields as scaffolding, and the third pass undoes it.
Step by step
- Guard the empty list. If
headisnil, returnnil. Later code readshead!.next, which would crash without the guard. - Start the first pass with
var node = headand loop whilenode != nil. - Save the original successor in
let nextNode = node!.next. Inserting the copy overwritesnode'snext, and the rest of the list would be unreachable without this saved reference. - Create the copy with
ListNode(node!.val). Only the value is copied now. - Splice it in:
node!.next = copyNodeand thencopyNode.next = nextNode. - Move to
nextNode, not tonode!.next. Moving to the copy would insert copies of copies forever. - Second pass. Reset
node = headand loop again. Each iteration reads the copy asnode!.next. - Copy the random link. If
node!.randomis notnil, setcopyNode!.random = node!.random!.next, which is the copy of the target. - Jump over the copy:
node = copyNode!.next, which is the next original, ornil. - Remember the answer.
let newHead = head!.nextis the first copy. It has to be saved before the third pass changeshead's link. - Third pass. Reset
node = head. For each original, take its copy and the next original,nextNode, which iscopyNode!.next. - Link the copies to each other: if
nextNodeexists,copyNode!.next = nextNode!.next. For the last pair the copy'snextis alreadynil. - Restore the original:
node!.next = nextNode. Then move on withnode = nextNode. - Return
newHead.
The solution in Swift
class Solution {
func copyRandomList(_ head: ListNode?) -> ListNode? {
if head == nil {
return nil
}
var node = head
while node != nil {
let nextNode = node!.next
let copyNode = ListNode(node!.val)
node!.next = copyNode
copyNode.next = nextNode
node = nextNode
}
node = head
while node != nil {
let copyNode = node!.next
if node!.random != nil {
copyNode!.random = node!.random!.next
}
node = copyNode!.next
}
let newHead = head!.next
node = head
while node != nil {
let copyNode = node!.next
let nextNode = copyNode!.next
if nextNode != nil {
copyNode!.next = nextNode!.next
}
node!.next = nextNode
node = nextNode
}
return newHead
}
}
Swift details to notice:
- Classes are references.
ListNodeis a class, sonode!.next = copyNodechanges the real node, andlet copyNodeis a constant reference to an object whose properties can still be assigned. That is whycopyNode.next = nextNodecompiles withlet. - Two kinds of optional. The first pass's
copyNodeis a plainListNode, because it was just created. In the later passescopyNodeisnode!.next, aListNode?, so those passes writecopyNode!. - The same loop condition throughout.
while node != nilworks on any optional without requiringListNodeto beEquatable. - Order matters in every assignment. Each pass first reads the links it will need later (
nextNode) into constants, and only then overwritesnext.
Complexity
Time: O(n). Three passes, each visiting every original node a constant number of times.
Space: O(1) extra. Apart from the n new nodes, which the answer needs anyway, the code keeps a few references. The interleaving reuses the existing next fields instead of a dictionary.
Edge cases and common mistakes
- Empty list. The guard returns
nilright away. - A single node.
[5,0], whose random points to itself, becomes5 → 5'after pass one, the copy's random becomes5.next, which is5', and the split returns one copy that points to itself. - Random to
nil. The second pass skips the assignment, and the copy keeps its defaultnil. - Random to an earlier or later node. Every copy exists after the first pass, so direction doesn't matter.
- Setting random links during the first pass. The target's copy might not exist yet.
- Skipping the split. The caller's list would keep the copies in the middle, and the copy list would still be tangled with it.
- Reading
head!.nexttoo late. After the split,head!.nextis the original second node. SavenewHeadbefore the third pass. - Forgetting to check
nextNodein the split. On the last pairnextNodeisnil, andnextNode!.nextwould crash.
Testing
[7,null], [13,0], [11,4], [10,2], [1,0]gives a list with the same values and random positions, and the original keeps its own links.[1,1], [2,1]gives the same structure, built from new nodes.[3,null], [3,0], [3,null]gives three new nodes with equal values and a random link only on the second, to the first.- An empty list gives
nil. [5,0]gives one new node whose random is itself.
