Copy List with Random Pointer (Reference) - Java

This method doesn’t use a HashMap.

Copy List with Random Pointer

/**
 * 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;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}

Related