LeetCode 138. Copy List with Random Pointer

Description

https://leetcode.com/problems/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.

Explanation

We can introduce a map to help us store the relationship between the original list node and the copy version new node.

Whenever we visited an original node, we can check if we have already created a copy version. If created, we use copy version to generate corresponding position new node in the new linked list.

Video Tutorial

Java Solution

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode current = dummy;
        RandomListNode newNode = null;
        
        while (head != null) {
            if (map.containsKey(head)) {
                newNode = map.get(head);
            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            }
            
            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    newNode.random = map.get(head.random);
                } else {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                }                
            }
            
            current.next = newNode;
            current = newNode;
            head = head.next;
        }
        
        return dummy.next;
    }
}

Leave a Reply

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