[Question]: Create a deep copy of the linked list. which consist of exactly n
fresh new nodes, where each new node has its value set to the value of its corresponding original node. Both the next
and random
pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X
and Y
in the original list, where X.random --> Y
, then for the corresponding two nodes x
and y
in the copied list, x.random --> y
.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]// with next & random pointers Output: head [[7,null],[13,0],[11,4],[10,2],[1,0]]
// Question--> Deep of Copy linked list
// Definition for a Node.
public class ListNodeWithRandom {
public var val: Int
public var next: ListNodeWithRandom?
public var random: ListNodeWithRandom?
public init(_ val: Int) {
self.val = val
self.next = nil
self.random = nil
}
}
func copyRandomList(_ head: ListNodeWithRandom?) -> ListNodeWithRandom? {
var iter = head, next = head
// First round: make copy of each node, and link them together side-by-side in a single list.
while iter != nil {
next = iter?.next
var copyList = ListNodeWithRandom(iter!.val)
iter?.next = copyList// poiting to New copy Node
copyList.next = next
iter = next
}
// Second round: assign random pointers for the copy nodes.
iter = head
while iter != nil {
if iter?.random != nil {
iter?.next?.random = iter?.random?.next
}
iter = iter?.next?.next
}
iter = head
var pseudoHead = ListNodeWithRandom(0)
var newCopy1 = pseudoHead, newCopy2 = pseudoHead
// Third round: restore the original list, and extract the copy list.
while iter != nil {
next = iter?.next?.next
// extract the copy
newCopy1 = iter!.next!
newCopy2.next = newCopy1
newCopy2 = newCopy1
// restore the original list
iter?.next = next
iter = next
}
return pseudoHead.next
}