Copy List with Random Pointer

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.

Solution:

  1. Add new node after each node
  2. Map the random pointer for each node to its corresponding new node
  3. Split the new nodes from the old linked list

Code:

/**
 * 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 {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return head;
        }
        addNewNode(head);
        mapRandomPointers(head);
        RandomListNode res = splitCopy(head);
        return res;
    }
    private void printList(RandomListNode head) {
        while (head != null) {
            System.out.print(head.label + "->");
            head = head.next;
        }
        System.out.println("Null");
    }
    private void addNewNode(RandomListNode head) {
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = new RandomListNode(head.label);
            head.next.next = temp;
            head = temp;
        }
    }
    //this function cannot be used independently. 
    private void mapRandomPointers(RandomListNode head) {
        while (head != null) {
            if (head.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }
    private RandomListNode splitCopy(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode curt = dummy;
        while (head != null) {
            curt.next = head.next;
            head.next = head.next.next;
            head = head.next;
            curt = curt.next;
        }
        return dummy.next;
    }
}

results matching ""

    No results matching ""