How to create deep copy of linked list who has random pointer

[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
}

Leave a Comment

Your email address will not be published. Required fields are marked *