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.

 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;
    }
}