CopyListWithRandomPointer.java

package design;

/**
 * Created by gouthamvidyapradhan on 11/03/2017. 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.
 *
 * <p>Return a deep copy of the list.
 */
public class CopyListWithRandomPointer {

  static class RandomListNode {
    int label;
    RandomListNode next, random;

    RandomListNode(int x) {
      this.label = x;
    }
  }

  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    RandomListNode one = new RandomListNode(1);
    one.next = null;
    one.random = one;
    /*RandomListNode two = new RandomListNode(2);
    RandomListNode three = new RandomListNode(3);
    RandomListNode four = new RandomListNode(4);
    RandomListNode five = new RandomListNode(5);
    one.next = two;
    two.next = three;
    three.next = four;
    four.next = five;
    one.random = three;
    two.random = five;
    three.random = null;
    four.random = two;
    five.random = four;*/
    RandomListNode result = new CopyListWithRandomPointer().copyRandomList(one);
    System.out.println();
  }

  private RandomListNode copyRandomList(RandomListNode head) {
    if (head == null) return null;
    RandomListNode ite = head, next;
    while (ite != null) {
      next = ite.next;
      RandomListNode node = new RandomListNode(ite.label);
      ite.next = node;
      node.next = next;
      ite = next;
    }

    ite = head;
    while (ite != null) {
      if (ite.random != null) ite.next.random = ite.random.next;
      ite = ite.next.next;
    }

    ite = head;
    RandomListNode copyIte = ite.next, copyHead = ite.next;
    while (copyIte.next != null) {
      ite.next = copyIte.next;
      copyIte.next = ite.next.next;
      copyIte = copyIte.next;
      ite = ite.next;
    }
    ite.next = null;

    return copyHead;
  }
}