138.md

138. Copy List with Random Pointer

Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Thinking Process

1. Create a dummy head which link to the actual list
2. For each node in the original list, create 2 new nodes with label values from node.next and node.random.

Code

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummyHead = new RandomListNode(0);
        RandomListNode current = dummyHead;
        
        while(head != null){
            current.next = new RandomListNode(head.label);
            current = current.next;
            if(head.random != null){
                current.random = new RandomListNode(head.random.label);
            }else{
                current.random = null;
            }
            head = head.next;
        }
        return dummyHead.next;
    }
}

Complexity

1. Time complexity is O(n)