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 = 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 = 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! = newCopy1
        newCopy2 = newCopy1
        // restore the original list
        iter?.next = next
        iter = next

Leave a Comment

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