How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)
Вставка
- Опубліковано 10 вер 2024
- 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
This is a classic interview problem for 1st and 2nd year interviews. I got this question in my interview for the Explore Microsoft Program.
Very simple. But we will still do this.
This is what I call a utility problem. Utility problems don't test your ability to think, they test your ability to do things such as traverse or manipulate data structures in often trivial (but not always) ways.
The brute force for this is to copy the linked list into a static structure like an array and then create a linked list from that...nah.
So the 2 ways we will really do it is to move the pointers around
Way 1 (Iterative):
For this approach we need to keep track of a prev and curr node. Why? This list is singly-linked so we can't get a node's predecessor, so during the traversal we must remember who came before the node we are at.
Before doing any of that we save the next node's address since if we move the node we are at's address, we would lose where to go next in the traversal.
Then finally we set the current node to the next node that we saved at the start of the iteration.
Complexities:
Time: O(n)
Space: O(1)
Way 2 (Recursive):
This is "top down" recursion, we start at the top and drill down. Then when we reach the bottom (the base case) we will come back upwards with the answer.
The recursive code will drill down in recursive calls until we get to the base case.
The base case gets triggered when the current node has no next, this means we are at the list's end, in that case we just return the node passed into the call.
Then the node before the last node has itself and the last node to work with.
We do some pointer movement.
Last node points to curr.
curr pointer to null since we don't know if this is the first node in the list.
first node will end up the last node in the list.
Then we return the head of the new linked list on the way back upwards.
The we repeat, what we get from the recursive call is a reversed list, we append our node to that list, and then return back upwards with an even longer reversed list.
In the top call we say:
"Reverse the rest of the list"
"Reverse the rest of the list"
"Reverse the rest of the list"
I'm the last node "Here I am 2nd to last node"
"processing"
3rd to last gets a reversed list, append
4th to last gets a reversed list, append
......and so on
Complexities:
Time: O(n)
Space: O(n)
Call stack space used.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Table of Contents: (This was one of the first videos I made. Audio sucks. Lighting sucks. It is pretty bad. I'm sorry.)
Intro & Video Setup 0:00 - 0:33
Problem Introduction 0:33 - 2:00
Iterative 2:00 - 6:08
Recursive 6:08 - 9:42
Recursive (Detailed Walkthrough) 9:42 - 13:26
Conclusion 13:26 - 13:49
For the recursive way forgot to stress the line saying "head.next = null", this ensures that you point the last node in the reversed portion (built slowly as we go upwards in the recursion) to null. This is important.
As for the recursive solution, I believe people are confused about head.next.next=head and head.next=null operations because they're not seeing that both rlh and head are referencing the same mutable node objects in heap.
In stack where head.data is 3:
rlh is 4
head is 3->4
head.next.next=head is 3->4->3->4...
head.next=null is 4->3, since it removes all "next" obj ref in 3 to 4, leaving intact 4->3
Since 4 now points to 3 in memory, rlh becomes 4->3
** debug the recursive solution in your IDE and place a breakpoint on line head.next=null. You will see that rlh.next is now node 3.
In stack where head.data is 2:
rlh is 4->3
head is 2->3
head.next.next=head, which is 2->3->2->3...
head.next=null is 3->2 2
Now rlh is 4->3->2 2
And now the main stack:
rlh is 4->3->2
head is 1->2
head.next.next=head is 1->2->1->2...
head.next=null is 2->1 , since the obj ref from 1 to 2 is removed
Now rlh is 4->3->2->1 , since 2 now points to 1.
Recursion is not easy to wrap your head around, especially when dealing with references (or pointers). You did a good job explaining the stack, but you missed the heap :)
Yeah, I was also wondering why use "head.next = null". Thank you, for clarifying this! Thanks for the video!
yo
Honestly I didn't really mind audio/lighting quality. But I think you could speak a little slower, because it kind of stresses me out when you speak so fast and it's also harder to understand that way. Beyond that, this was a really nice explanation!
@@irfaanjamarussadiq5500 old video
I never imagined learning code would be this intense
lmao
🤣
I like your comment, it is a bitter true a few people discuss lol
This is literally the best explanation of reversing a linked list on youtube!!!
thx
You seem so excited to explain the problems, it makes your videos engaging 😁
But honestly this is some of the best interview prep that I've gotten, especially since I'm a visual learner.
Great! :) -Ben
No one can explain recursive thinking better than you, man. Respect
hahaha thanks
I found myself smiling as I watched this video because your passion and enthusiasm really shone through. Great explanation and good work!
Great to hear!
I have been preparing interviews for data scientist positions, and the coding part of the job is not too easy for a person without a computer science background. I was struggling in understanding the recursion function for a really long time, and this is the first time I finally understand it intuitively after watching your video. Thank you so much! Your call stack illustration helps a ton!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
lol I love how you are so enthusiastic about this :D
ya
12:58 Hahaha, explanation with synchronized movements is hilarious bro. Respect.
ye
Kind of makes me miss college. I would also get really excited when I finally understood something and was explaining it to someone. Thank you for helping me understand it.
Sure. great.
This guy explains reversing a linked list like playing basketball with all the shoes' sound lol, love your enthusiasm ;)))
hey
I’ve been struggling with DSA, but the way you taught this really opened my eyes. I’ll admit, I watched a few parts several times, but I love your energy and will definitely be returning for future problems!
You explain recursion like no one in their wildest dreams can even think of !!!!
saw this video for reversing a linked list recursively . Helped me a lot . Thanks man !
great - sure
thank you for framing this as pointer manipulation instead of "moving nodes" like so many tutorials do
sure
you explanation on recursive method was pretty clear
great glad it helped
Explains recursion so well. Thank you.
Yea I subscribed. You had me on the edge of my seat the entire video like I'm watching a suspenseful movie.
haha thanks for the sub
bruh this is a treasure on youtube. thank you!
Thank you,, NEXT
hahahahahahahahahaha. Best comment on this whole channel. I love you.
you're so good at explaining!. thanks !!
Thanks! try out the 5 day free mini course backtobackswe.com/
Damn! this is the best video I found. It just cleared all my doubts for reversing a linked list recursively. Thanks for the video.
The time i see that you had made a video on this i know that my doubt is going to get resloved before the video gets over and it happened :)
Never seen anyone this excited about reversing a linked list, haha
I am a lively guy
Thnx! Finally, I got this logic of returning back after top to bottom😄
Thank you! The iterative explanation and diagram was so helpful for me. I was able to implement the function without looking at a code example, but from imagining the diagram you created.
nice
Idk how you can be so excited talking about recursion but it's making me excited!!!
The intention & intensity with which you explain is commendable. You deserve more subscribers. I subscribed! 😊
Ahhh please make more videos!!! You are such a lifesaver I swear. Watched your video like 5 times to really understand the concept. Maybe on recursion and more data structures. Also, a suggestion, try to talker slower :)
Thanks and we will
Brother no words for you . i am stuck at temp->next->next but you nailed it with the example "Let me Add myself"
Lot's of love from india
hey
my homie always there to help me with data structures
OMG... Thank you so much for your amazing teaching skills!
I am happily crying since this finally makes sense to me after all that struggle...
thanks and nice haha
Hey man, thanks for this video. It's such a simple an elegant solution. I spent the last 12 hours trying to solve it myself (not too smart really) and finally gave up and came here. Your explanation is so clear. Cheers!
Just because you couldn’t solve it doesn’t mean you are “not too smart”. It could just be a difference in coding experience. I wouldn’t get down on yourself. You’re already doing great and setting yourself up for success by working hard to get better and watching videos like this!
Best video on recursion I have ever watched
I thought the recursive way was really confusing so I had to look it up on UA-cam. Really glad I found this video. Amazing explanations!
haha nice, wassup
I came here for the recursive method and the explanation was great! keep it up!
sure
Best explanation out there
Thanks man
thanks
Finally a simple explanation. Thanking God for creating you 😁 😁 😁 😁 😁
now THAT is how you explain recursion
If I had a teacher as enthu as u bout teaching I would have been better programmer today...appreciate your efforts
thanks
I watched so many explanations regarding this i could not understand but i got an idea about this by watching your video .
Kudos !!!
thanks
One of the more clear explanations of this god forsaken problem. Thank you
every one is asking how he is so enthusiastic but my mannnn took a preworkout and he is getting the pre workout kick!!!!
Thanks Handy Dandy,now i can reverse a linked list,have a blessed day.
great
this is the best explanation of this concept
Hahaa yay
Bro thanks alot man I final understand this stuff, thanks so much😭
this is the best explanation for listNode reverse! Really appreciate it !!
It took a while to sink in, but thanks for this detailed explanation to the problem. You killed it
thx
I love your enthusiasm. It makes it so much more fun to learn.
Thanks buddy, I like your explanation better than other's.
nice
This is literally the best explanation I have come across🙌
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Absolutely the best video to explain this. Just took away all my frustration lol!!
Finally, I got it! Thank you so much for your video! Your channel is a hidden jam!
thanks!
I can only hope that one day I can explain this with as much excitement and clarity as you do.
I finally understand this. Thank you.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Paid for a DSA course on Udemy and ended up have to UA-cam because the explanations were trash. You explained it beautifully and made it incredibly easy to understand. Before finding this video I was dumber than a rock.
Glad it helped
Oh your energy 🔥🔥🔥 I was going to sleep but now I will have a big brain time evening 😆😆😆 thanks so much!
Haha so glad!
tysm man ...you literally nailed it with this explanation .....finally i understood how to do this now.
Wow! Leetcode had only 250 problems when this video was recorded. Now it has crossed the event horizon lol!
No it had 780, I just aimed to do 250 problems that hit core concepts since most of their problems just repeat core ideas.
@@BackToBackSWE Hey man. it was the best explanation for the reversal link list. it doesn't take a second try.
@@BackToBackSWE True, that makes a whole lot of sense.
i have seen many videos but urs is awesome and the best
thanks.
Thanks for the beautiful explanation
sure
dude this guy is awesome i wish he was my professor
Thanks, finally understand the recursive solution. The explanation of call stack really helps.
thanks
Had to rewind a lot but first video that worked to understand it :)
10:40 so we have head that points to 3 and new_head(reversedHead) that points to 4.
Overall, since each time we have a function call with a new/subsequent head, once we start returning, the head is going to be updated for each call in the reversed order once we propagate back/up the stack, but new_head/reversed will stay the same (we set it value once when we reach the depth of the calls) and always points to 4, so we return it at the end of the whole function.
Thanks for the video! You simplified this so much for me!
Sir the way you give so comprehensive explanation... I love it!
love your videos, keep up the great work.
thanks
Love from India..🇮🇳🇮🇳
thanks
THE BEST VIDEO ON UA-cam !!!!!!!! IM IN LOVE :)
Awesome! One thing missing is head.next = null, because that link is not needed anymore.
My man big on energy. Love it!
Really love your illustration! Thank you!!
took me sometime for me to digest. thank you.
This guy is probably the most passionate CS guy in the entire universe!
Great explanation!!! gonna use your videos for interview prep. Many thanks 🙇
great!
really love his way to explain this question🤣
he is so enthusiastic and energetic!
Thank you man, helped me to understand this f***ing recursive approach
Very good explanation. I've watched a few of your videos and all of them so far have been easy to follow and does a good job of explaining the approach.
thanks, welcome to the tribe 🍖
Watching your explanation and just the passion that you put into these videos really helped me remember the nuances of this problem.
great
That was really helpful man. I'm grateful! Keep up with the good work!
Happy Holidays 🎉 Thank you for your kind words! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
Explanation is crystal damn clear.
thx
WAAAH I FINALLY UNDERSTAND IT BROO!!!
great
I really liked your explanation on the recursive method bro thanks
great explanation....I am able to visualize the recursion while you explain
Thank you, means a lot 🎉 You can also check out our free DSA course - backtobackswe.com/
omg you are a life savior
best explanation of reverse singly link list
Do you have any DSA course ?
I got the logic by 3:20 you are really dope at this.
haha thx
These videos are amazing. You're a phenomenal instructor.
Thanks man! subscribe to my DSA course for some amazing content b2bswe.co/3HhvIlV
Life saver bro
Thanks for your kind explanation
This guy is something elese 🚀
This is why online learning is so much more Superior to in person lectures. In person it would probably go way over your head. But on UA-cam you can pause and rewind as many times as you want until it clicks
haha nice, this video is old and not that good
@@BackToBackSWE it's pretty good. I still find the recursive part a bit confusing though. I know it's common for employers to ask how to reverse it iteratively but do you think it's common for them to ask to do it recursively?
Thank you for this well informed video!
this was awesome and helped me out a lot. Thank you!
Best Explanation, thank you! I think you have to write the recursive version yourself and draw the nodes to really get it.
Yes
incredible explanation. THANK YOU
How can someone thumbs down this video !!! Amazing effort and urge to explain the solution !!!
thanks
Great Teacher man! Finally got the recursion when you could help me visualize going downwards then backup. Thank you man!!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Such a thorough and simple explanation. Thank you!
sure
Great Job and great explanation. You take so much effort to explain. Thanks so much!!
sure