138. Copy List with Random Pointer

// LeetCode URL: https://leetcode.com/problems/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;
//     }
// };

/**
 * Iterative with constant extra space
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Number of nodes in input list.
 */
class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        RandomListNode current = head;
        while (current != null) {
            RandomListNode nodeCopy = new RandomListNode(current.label);
            nodeCopy.next = current.next;
            current.next = nodeCopy;
            current = nodeCopy.next;
        }

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

        RandomListNode dummyNewListHead = new RandomListNode(-1);
        RandomListNode currentNewList = dummyNewListHead;
        current = head;

        while (current != null) {
            currentNewList.next = current.next;
            current.next = current.next.next;
            current = current.next;
            currentNewList = currentNewList.next;
        }

        return dummyNewListHead.next;
    }
}