138 Copy List with Random Pointer¶

Problem¶

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.

Solutions¶

/**
 * 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) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode original = head;
        while (original != null) {
            RandomListNode node = new RandomListNode(original.label);
            map.put(original, node);
            original = original.next;
        }
        original = head;
        while (original != null) {
            RandomListNode copied = map.get(original);
            copied.next = map.get(original.next);
            copied.random = map.get(original.random);
            original = original.next;
        }
        return map.get(head);
    }
}

/**
 * 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;
        }
        RandomListNode node = head;
        while (node != null) {
            RandomListNode copied = new RandomListNode(node.label);
            copied.next = node.next;
            node.next = copied;
            node = node.next.next;
        }
        node = head;
        while (node != null) {
            System.out.println(node.label);
            node = node.next;
        }

        RandomListNode res = head.next;
        node = head;
        while (node != null) {
            RandomListNode copied = node.next;
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        node = head;
        while (node != null) {
            RandomListNode copied = node.next;
            node.next = copied.next;
            node = copied.next;
            copied.next = node == null?null:node.next;

        }
        return res;
    }
}