LeetCode 138: Copy List with Random Pointer

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.

/**
 * 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 {
    public RandomListNode copyRandomList(RandomListNode head) {
        // Return a duplicate list of original list
        // Original list: A B C D
        // Step 1: Create and insert duplicates into original list: A A' B B' C C' D D'
        // Step 2: Copy random pointer of original list to that of duplicate list
        // Step 3: Split and return the duplicate list
        if (head == null)
            return null;
            
        insert(head);
        copy(head);
        return split(head);
    }
    
    // Create and insert duplicates into original list
    private void insert(RandomListNode head)
    {
        // Note: The list structure is changed; node = node.next should be changed to node = node.next.next
        for (RandomListNode node = head; node != null; node = node.next.next)
        {
            RandomListNode dup = new RandomListNode(node.label);
            
            dup.next = node.next;
            node.next = dup;
        }
    }
    
    // Copy random pointer of original list to that of duplicate list
    private void copy(RandomListNode head)
    {
        for (RandomListNode node = head; node != null; node = node.next.next)
            if (node.random != null)
                node.next.random = node.random.next;
    }
    
    // Split and return the duplicate list
    private RandomListNode split(RandomListNode head)
    {
        RandomListNode dup = head.next;
        
        for (RandomListNode node = head; node != null; node = node.next)
        {
            RandomListNode tmp = node.next; // Note: The structure should be changed. We should temporarily save the duplicate.
            
            node.next = node.next.next;
            
            if (tmp.next != null)
                tmp.next = tmp.next.next;
        }  
            
        return dup;
    }
}