LeetCode 138: Copy List with Random Pointer Solution

Master LeetCode problem 138 (Copy List with Random Pointer), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

138. Copy List with Random Pointer

Medium

Hash Table Linked List

Problem Explanation

Explanation

To deep copy a linked list with random pointers, we first create a new node for each original node and insert it next to the original node. Then we update the random pointers of the new nodes based on the random pointers of the original nodes. Finally, we separate the original and copied linked lists to get the deep copy.

Algorithm:

Iterate over the original linked list and create a new node for each node. Insert the new node next to the original node.
Iterate again over the combined list and update the random pointer of the new nodes based on the random pointer of the original nodes.
Separate the combined list into two separate linked lists: original and copied.

Time Complexity: O(N) where N is the number of nodes in the linked list.

Space Complexity: O(N) for creating new nodes in the copied list.

Solution Code

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public Node copyRandomList(Node head) {
    if (head == null) return null;

    // Step 1: Create new nodes next to original nodes
    Node curr = head;
    while (curr != null) {
        Node newNode = new Node(curr.val);
        newNode.next = curr.next;
        curr.next = newNode;
        curr = newNode.next;
    }

    // Step 2: Update random pointers of new nodes
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }

    // Step 3: Separate original and copied linked lists
    Node original = head;
    Node copied = head.next;
    Node copiedHead = head.next;

    while (original != null) {
        original.next = original.next.next;
        copied.next = (copied.next != null) ? copied.next.next : null;
        original = original.next;
        copied = copied.next;
    }

    return copiedHead;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 138 (Copy List with Random Pointer)?

This page provides optimized solutions for LeetCode problem 138 (Copy List with Random Pointer) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 138 (Copy List with Random Pointer)?

The time complexity for LeetCode 138 (Copy List with Random Pointer) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 138 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 138 in Java, C++, or Python.

Back to LeetCode Solutions