Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution 

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given a standard linked list with next pointer BUT each node carries an additional random pointer to any given node in the linked list. Clone the linked list.
Let us first see the mental barriers and problems that we face while solving this.
It is trivial to make a copy of the linked list nodes with only the next pointers, but the random pointer on each node presents a problem.
We will notice that we have trouble establishing the connection between the original linked list and the random pointers between nodes in the cloned linked list.
Approach 1 (Linear Space Solution)
Use a hashtable to facilitate the cloning.
Complexities
Time: O( n )
We will perform linear time traversals that keep our asymptotic behavior linear.
Space: O( n )
We will store a clone mapping for each node entailing linear space complexity with respect to the original list passed to us.
Approach 2 (Constant Space Solution)
Use the original list's node's next pointer to map to the clone list.
Complexities
Time: O( n )
We are still only doing linear time traversals
Space: O( 1 )
We do not store any auxiliary space that will scale as the input size gets arbitrarily large.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question on Leetcode: leetcode.com/p...