Copy List with Random Pointer

Problem

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.

Challenge

Could you solve it with O(1) space?

Code - Java

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

        RandomListNode n = head;
        while (n != null) {
            RandomListNode copy = new RandomListNode(n.label);
            copy.next = n.next;
            n.next = copy;
            n = copy.next;
        }

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

        RandomListNode old = head;
        RandomListNode newHead = head.next;
        n = head.next;
        while (n.next != null) {
            RandomListNode tmp = n.next;
            n.next = n.next.next;
            old.next = tmp;
            old = old.next;
            n = n.next;
        }
        return newHead;
    }
}