Start learning free

LESSON 435 OF 671 · LINKED LISTS

Copy List with Random Pointer in Java (O(n) Time Complexity)

Practice O(n) Read the full explanation

You get the head of a linked list. Build a deep copy of it and return the copy's head.

Each node has a value, a next pointer and one more pointer, random. This random pointer can lead to any node of the list, even the node itself. It can also be null.

The copy is made only of new nodes, one for each original node, with the same values. In the copy, each next and random leads to the matching new node. Nothing points back into the original list.

Say an original node's random leads to the third node. Then its copy's random leads to the copy of the third node.

The examples describe the list with two arrays of the same length. The first, values, holds the values from the head on. The second, random, holds one entry per node. For node i, random[i] is the index of the node its random leads to. Indexes start at 0, and null means no node.

Your function gets only head.

 

Example 1:

4 9 1 6 null next random
Input: values = [4,9,1,6], random = [null,3,0,2]
Output: values = [4,9,1,6], random = [null,3,0,2]
Explanation: The dashed blue arrows are the random pointers.
The copy has four new nodes with the same links:
the new 4's random is null,
the new 9's random leads to the new 6,
the new 1's random leads to the new 4,
the new 6's random leads to the new 1.

Example 2:

8 8 null next random
Input: values = [8,8], random = [null,0]
Output: values = [8,8], random = [null,0]
Explanation: Both nodes hold 8.
The second 8's random leads to the first 8.
In the copy, it must lead to the new first 8, not the old one.

Example 3:

7 next random

Input: values = [7], random = [0]
Output: values = [7], random = [0]
Explanation: The only node's random leads to itself.
In the copy, the new node's random leads to the new node.

 

Constraints:

  • 0 to 1,000 nodes.
  • For an empty list (head is null), return null.
  • Each value is from -10,000 to 10,000.
  • Each random is null or leads to a node of the same list.

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 11
    Ctrl + Enter to check

    JAVA · LINKED LISTS

    Copy List Random Pointer in Java, explained

    Understanding the Problem

    The core challenge of this problem is to create a deep copy of a linked list where each node has an additional random pointer. The deep copy should be a completely new list with no shared references to the original list. This problem is significant in scenarios where data integrity and isolation are crucial, such as in cloning complex data structures or undo mechanisms in applications.

    Approach

    To solve this problem, we can break it down into three main steps:

    1. First, create a copy of each node and insert it right next to the original node in the list.
    2. Second, assign the random pointers for the copied nodes.
    3. Finally, separate the copied nodes to form the new deep copied list.

    Step-by-Step Algorithm

    Let's break down the algorithm in detail:

    1. Copy Nodes: Traverse the original list and create a new node for each original node. Insert each new node right after its corresponding original node.
    2. Assign Random Pointers: Traverse the list again to assign the random pointers for the copied nodes. If the original node's random pointer is not null, set the copied node's random pointer to the copied version of the original node's random pointer.
    3. Separate Lists: Finally, traverse the list a third time to separate the original and copied nodes, restoring the original list and forming the new deep copied list.

    Code Implementation

    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    
    public class Solution {
        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }
    
            // Step 1: Create a copy of each node and insert it right next to the original node.
            Node current = head;
            while (current != null) {
                Node newNode = new Node(current.val);
                newNode.next = current.next;
                current.next = newNode;
                current = newNode.next;
            }
    
            // Step 2: Assign random pointers for the copied nodes.
            current = head;
            while (current != null) {
                if (current.random != null) {
                    current.next.random = current.random.next;
                }
                current = current.next.next;
            }
    
            // Step 3: Separate the copied nodes to form the new deep copied list.
            current = head;
            Node newHead = head.next;
            Node copy = newHead;
            while (current != null) {
                current.next = current.next.next;
                if (copy.next != null) {
                    copy.next = copy.next.next;
                }
                current = current.next;
                copy = copy.next;
            }
    
            return newHead;
        }
    }
    

    Complexity Analysis

    The time complexity of this algorithm is O(n) because we traverse the list three times, each taking linear time. The space complexity is also O(n) due to the space required for the new nodes.

    Edge Cases

    Consider the following edge cases:

    • An empty list (head is null).
    • A list where all random pointers are null.
    • A list where random pointers form a cycle.

    Our algorithm handles these cases effectively by ensuring that the deep copy is accurate and isolated from the original list.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple lists with no random pointers.
    • Lists with random pointers pointing to various nodes, including themselves.
    • Edge cases such as empty lists and single-node lists.

    Conclusion

    Understanding and solving the "Copy List with Random Pointer" problem is crucial for mastering deep copy techniques in linked lists. By breaking down the problem and following a structured approach, we can create an efficient solution that runs in O(n) time and uses O(n) extra space.

    Additional Resources

    For further reading and practice problems, consider the following resources:

    Keep going with Java650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free