# Copying a List with Random Pointer in Java – LeetCode

Copying a linked list with random pointers is a classic problem in computer science and is commonly asked in technical interviews. In this article, we will explore how to solve this problem using Java like on hackernoon.com/java-algorithms-copying-list-with-random-pointer-leetcode.

## The Problem Statement

The problem is as follows: You are given a linked list where each node has two pointers – a next pointer pointing to the next node in the list, and a random pointer pointing to a random node in the list. You need to make a deep copy of the original list.

This means that for each node in the original list, you should create a new node in the copied list with the same value, and the copied list’s next pointer should point to the copied next node, and the copied list’s random pointer should point to the copied random node.

## Approach 1: Using a Hash Map

One way to solve this problem is by using a hash map to keep track of the mapping between nodes in the original list and nodes in the copied list. Here are the steps to do this:

• Create an empty hash map where the keys are nodes in the original list, and the values are nodes in the copied list.
• Iterate through the original list, and for each node, create a new node in the copied list with the same value.
• Put the mapping between the original node and the copied node into the hash map.
• Iterate through the original list again, and for each node, set the next pointer and random pointer of the copied node based on the mapping stored in the hash map.
```// Java code to copy a linked list with random pointers
class Node {
int val;
Node next;
Node random;

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

return null;
}

Map<Node, Node> map = new HashMap<>();

// First pass: create new nodes and map them
while (current != null) {
map.put(current, new Node(current.val));
current = current.next;
}

// Second pass: assign next and random pointers
while (current != null) {
Node newNode = map.get(current);
newNode.next = map.get(current.next);
newNode.random = map.get(current.random);
current = current.next;
}

}```

This approach has a time complexity of O(N) where N is the number of nodes in the linked list, and a space complexity of O(N) due to the hash map.

## Approach 2: Modifying the Original List

Another approach to solve this problem is by modifying the original list itself to create the copied list. Here are the steps:

• For each node in the original list, create a new node with the same value and insert it immediately after the original node.
• Iterate through the modified list, and for each node, set its random pointer to the node after its random pointer in the original list.
• Split the modified list into two separate lists – the original list and the copied list.
```// Java code to copy a linked list with random pointers by modifying the original list
return null;
}

// Step 1: Duplicate each node and insert it after the original node
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}

// Step 2: Set random pointers for the copied nodes
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}

// Step 3: Split the original list and the copied list
while (p1 != null) {
p1.next = p2.next;
p1 = p1.next;
if (p1 != null) {
p2.next = p1.next;
p2 = p2.next;
}
}