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

📹 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.

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

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

[BackToBackSWE]

Table of Contents:

Me Talking 0:00 - 0:32
The Problem Introduction 0:32 - 1:43
Assessing What We Know 1:43 - 1:59
Finding Our Mental Barriers 1:59 - 4:09
The Hashtable Breakthrough 4:09 - 4:47
Linear Space Solution Walkthrough 4:47 - 9:33
Can We Do Better? :) 9:33 - 10:55
Constant Space Solution Walkthrough 10:55 - 16:46
Wrap Up 16:46 - 17:19

The code for this question is in the description. Both the linear space and constant space solutions are addressed.

[rishabkumar]

I just got placed in Amazon and I want to extend my deepest thanks to you. You helped me a lot man!! Thank you and all the best for your amazing channel

[dirkneuhauser]

Finally someone who likes to explain stuff and who does it enthusiastically. It's a pleasure to watch! !! Thanks ma dud! :)

[tapasyak]

I just found your channel and hands down this is THE BEST in terms of teaching how to solve a coding problem. Most of the videos I see just have the answer in hand and they try to explain how that answer works. But nobody tries to tell you how to come up with that answer ourselves first with common sense. This video exactly has what other's are lacking. On top of that, see that enthusiasm in that guy. I love him!

[MultiPriya]

You are the first teacher who has made me fall in love with DS..
I never thought I would ever dare to solve such kinda problems.. :D I started with quick sort and here I am..
Great explaination! And to all the followers : Just watch the video in fast forward mode.. !!!! ;D

[cryptojeff]

This is awesome! Clear explanation. Lost my job offer because of coronavirus and preparing for interviews.

[MiddleEasternInAmerica]

so far, that's my favorite video on BackToBackSWE channel, I smile everytime he says "again the code in the description" :)

[paul-mwpc]

great stuff, I didn't even understand the question being asked on the leetcode page. Your diagram helped a ton, thank you.

[lugiadark]

When I first read the question I was like WTF I cannot solve this, after seeing your video I was able to code it without looking at the code. Thanks again!! Your videos are the best!!

[yanxichen]

Well, I for one am glad you failed this question for that interview then... am I allowed to say that? lol Great video as always.

[sanjanachopra]

If not for this video, I wouldn't have understood the question itself. Thank you so much for all your videos☺️

[vishnuvardhan]

When I first saw the question, I thought it was just similar to clone graph and other thing is we should not mess up with original linked list pointers.But messing up with original linked list pointers gave the constant space solution😱.Awesome explaination!

[yvestuyishime]

If i get this question for the first time, i would cry!!!

[RitikSharma-pcyj]

WOW!! Without this problem, the Linked list are incomplete :) Thanks for whatever you taught us

[CrazyHunk]

to be really honest i just got stuck with the same problem in my interview. where i was about to discover the constant space solutions but i could not(interview pressure) then i came back to your channel and found out you too. now i am felling well about myself. still i am gonna binge all your videos thanks for helping you are doing a great job.

[rishabkumar]

I was asked this question in an interview today and I got it right just because of you!! Thanks man

[osamaxz]

you are one of the best teachers, I solved it in O(n^2) and I don't watch your videos to see the solution as I really watch to see how to think, my thinking was near to yours but surly your is better and helped me a lot of learning how to think in more efficient way, thanks <3

[remykhayat]

i spent hours trying to do this and even tho the constant space answer is non-trivial you made it very easy to understand, thank you sooo much, i hope i see this question in my next interview

[amospan]

Thank you for failing this interview question and instead of letting it define you as a failure, you used it as motivation to teach all of us. I appreciate it my man! =)

[tonybernoulli]

This is far more clear than any tutorial I watched on youtube, please make more videos like this