Copy List with Random Pointer

Copy List with Random Pointer

27%

Accepted

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.

Have you met this question in a real interview? 

Yes

Example

Challenge

Could you solve it with O(1) space?

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) {

        // write your code here

        if(head == null) return head;

        RandomListNode dummy = new RandomListNode(0);

        dummy.next = head;

        RandomListNode run = head;

        while(run != null){

            RandomListNode copy = new RandomListNode(run.label);

            RandomListNode temp = run.next;

            run.next = copy;

            copy.next = temp;

            run = temp;

        }

        

        run = head;

        while(run != null){

            if(run.random != null){

                run.next.random = run.random.next;

            }

            run = run.next.next;

        }

        run = head;

        RandomListNode newHead = run.next;

        while(run != null){

            RandomListNode temp = run.next;

            run.next = temp.next;

            if(temp.next != null)

                temp.next = temp.next.next;

            run = run.next;

        }

        return newHead;

        

    }

}