Clone Linked List with Random and Next Pointer
Hard Problems of Linked List DSA practice problem on Onlearn.
Difficulty: hard.
Topics: How to create a deep copy of a linked list with next and random pointers?, Linked List, Node, Pointer, Algorithm, Time Complexity, Space Complexity, Big O Notation, Map, Hash Tables, Brute Force, Optimization, In-place Algorithm, space complexity, node operations, general programming, pointer operations, time complexity analysis, hash map, linked list, Cloning a Linked List, Flattening a Linked List.
Problem Statement Given a linked list where each node has two pointers: next which points to the next node in the list, and random which points to a random node in the list or null. Your task is to create a 'deep copy' of the given linked list and return its head. Input Specification The input will be the head of a linked list. Each node in the list contains an integer data value, a next pointer, and a random pointer. The next pointer points to the subsequent node in the sequence, and the random pointer can point to any node in the list, including itself, or null. Output Specification Return the head of the deep copied linked list. The copied list must be completely independent of the original list, meaning new nodes must be created, and all next and random pointers in the new list must point to the appropriate new nodes. Sample Test Case Input: A linked list represented as follows: Node 1: data = 7, next = Node 2, random = Node 3 Node 2: data = 14, next = Node 3, random = Node 1 Node 3: data = 21, next = Node 4, random = Node 4 Node 4: data = 28, next = null, random = Node 2 Visually: 7 (random 21) 14 (random 7) 21 (random 28) 28 (random 14) null Output: A deep copy of the input linked list, maintaining identical data values and pointer relationships among the new nodes. Visually: 7 (random 21) 14 (random 7) 21 (random 28) 28 (random 14) null (This represents a new list with new nodes, but the same logical structure and values as the input.)