Copy List with Random Pointer

Difficulty: Medium | Category: LinkedList | Asked at: Amazon | Platform: Unfoldd Arena

**Copy List with Random Pointer** ===================================================== **Problem Statement** ------------------- Given a linked list with a random pointer, create a deep copy of the list. The random pointer is a reference to a node that is randomly chosen from the linked list. **Rules and Constraints** ------------------------ - The linked list is represented as a graph, with each node having a reference to its next node and a random node. - The input linked list may contain duplicate nodes. - The output should be a completely separate copy of the input linked list, with no references to the original list. - Time complexity: O(N), where N is the number of nodes in the linked list. - Space complexity: O(N), where N is the number of nodes in the linked list. - Nodes are represented as instances of a Node class with int val, Node next, and Node random attributes. Note that the random node may be the same node or a different node. However, each node in the original list will only have one random pointer. The random pointer of a node can point to any node in the linked list, including itself. ### Example **Input:** {"head":"[[7,null],[13,0],[11,4],[10,2],[1,0]]"} **Output:** "deepCopy"

Solve Copy List with Random Pointer online for free in Python, JavaScript, Java, C++, TypeScript, Go, Rust, PHP, Swift, Kotlin, Dart, Ruby, C, and C#. Practice Medium level coding interview problems with instant test case evaluation and AI-powered analysis.

Keywords: Copy List with Random Pointer solution, Copy List with Random Pointer leetcode, Copy List with Random Pointer python, Copy List with Random Pointer javascript,Copy List with Random Pointer java, Copy List with Random Pointer approach, how to solve Copy List with Random Pointer, medium coding problems, LinkedList problems, coding interview preparation, DSA practice free.

Copy List with Random Pointer

Medium

Copy List with Random Pointer

Problem Statement

Given a linked list with a random pointer, create a deep copy of the list. The random pointer is a reference to a node that is randomly chosen from the linked list.

Rules and Constraints

  • The linked list is represented as a graph, with each node having a reference to its next node and a random node.
  • The input linked list may contain duplicate nodes.
  • The output should be a completely separate copy of the input linked list, with no references to the original list.
  • Time complexity: O(N), where N is the number of nodes in the linked list.
  • Space complexity: O(N), where N is the number of nodes in the linked list.
  • Nodes are represented as instances of a Node class with int val, Node next, and Node random attributes.

Note that the random node may be the same node or a different node. However, each node in the original list will only have one random pointer. The random pointer of a node can point to any node in the linked list, including itself.

Example

Input: {"head":"[[7,null],[13,0],[11,4],[10,2],[1,0]]"} Output: "deepCopy"

CompaniesAmazon
JavaScript

Login to write code

Solve problems, verify your skills, and earn XP.