Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution @BackToBackSWE
Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution  @BackToBackSWE
Uploaded January 2019 | Updated November 2026, 3 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πŸ“Ή 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: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

++++++++++++++++++++++++++++++++++++++++++++++++++

This question on Leetcode: leetcode.com/problems/copy-list-with-random-pointer
Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space SolutionTotal Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)Implement An LRU Cache - The LRU Cache Eviction Policy (LRU Cache on LeetCode)Depth First & Breadth First Graph Search - DFS & BFS Graph Searching AlgorithmsSearch A Maze For Any Path - Depth First Search Fundamentals (Similar To The Maze on Leetcode)Why Comparison Based Sorting Algorithms Are Ξ©(n*lg(n))Implement A Queue Using Stacks - The Queue ADT (Implement Queue Using Stacks on LeetCode)Test If A Binary Tree Is Symmetric (Symmetric Tree on Leetcode)3 Mistakes Beginners Make When First Learning Java and Android DevelopmentTotal Ways To Decode A String - Recursive Dynamic Programming Approach (Decode Ways on LeetCode)Explained | Flow Network #shorts #datastructures #codinginterview #dsaThe Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms
Back To Back SWE |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER