algoadvance

Leetcode 138. Copy List with Random Pointer

Problem Statement

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.

The Linked List is represented by a node class with attributes:

Clarifying Questions

  1. Are the val attributes guaranteed to be unique?
  2. Can the random pointer also point to null?
  3. Should we assume the input might be an empty linked list?

Strategy

The problem can be approached by creating a new node for each original node and setting up the appropriate next and random pointers. We’ll split the process into three main steps:

  1. Step 1: Clone the Nodes: Create new nodes and insert them just next to the original nodes. This way, for each original node, we will have a new node immediately following it.
  2. Step 2: Set Up Random Pointers: Iterate through the modified list and set the random pointers for the new nodes.
  3. Step 3: Separate the Lists: Finally, separate the new nodes from the original nodes to form the new list.

Code

Here’s the implementation in Java:

// Definition for a Node.
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 new nodes and add them next to original nodes
        Node iter = head;
        while (iter != null) {
            Node newNode = new Node(iter.val);
            newNode.next = iter.next;
            iter.next = newNode;
            iter = newNode.next;
        }

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

        // Step 3: Separate the original list and the new list
        iter = head;
        Node newHead = head.next;
        while (iter != null) {
            Node newNode = iter.next;
            iter.next = newNode.next;
            iter = iter.next;
            if (newNode.next != null) {
                newNode.next = newNode.next.next;
            }
        }

        return newHead;
    }
}

Time Complexity

The time complexity of this solution is (O(N)), where (N) is the number of nodes in the linked list. This is because we traverse the list a constant number of times (three passes).

  1. First pass: Create new nodes inserted among original nodes.
  2. Second pass: Set the random pointers for the new nodes.
  3. Third pass: Separate the new list from the original list.

Space Complexity

The space complexity is (O(1)) because no additional space proportional to the input size is used; we are modifying the existing list structure.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI