How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)
ฝัง
- เผยแพร่เมื่อ 7 ก.ย. 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
![Megan Thee Stallion - Neva Play (feat. RM) [Official Video]](http://i.ytimg.com/vi/TpYTyAaTRts/mqdefault.jpg)
![[TH] 2024 PMSL SEA Finals D1 | Fall | ยิงต้องโหด ให้เหมือนโกรธกันมาก่อน](http://i.ytimg.com/vi/OnTdfGySmds/mqdefault.jpg)
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
No one can explain recursive thinking better than you, man. Respect
hahaha thanks
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
lol I love how you are so enthusiastic about this :D
ya
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 😀
This guy explains reversing a linked list like playing basketball with all the shoes' sound lol, love your enthusiasm ;)))
hey
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.
You explain recursion like no one in their wildest dreams can even think of !!!!
thank you for framing this as pointer manipulation instead of "moving nodes" like so many tutorials do
sure
Never seen anyone this excited about reversing a linked list, haha
I am a lively guy
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!
saw this video for reversing a linked list recursively . Helped me a lot . Thanks man !
great - sure
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
Idk how you can be so excited talking about recursion but it's making me excited!!!
bruh this is a treasure on youtube. thank you!
Thank you,, NEXT
hahahahahahahahahaha. Best comment on this whole channel. I love you.
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
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
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!
my homie always there to help me with data structures
Explains recursion so well. Thank you.
you explanation on recursive method was pretty clear
great glad it helped
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 :)
I can only hope that one day I can explain this with as much excitement and clarity as you do.
The intention & intensity with which you explain is commendable. You deserve more subscribers. I subscribed! 😊
Thanks Handy Dandy,now i can reverse a linked list,have a blessed day.
great
Damn! this is the best video I found. It just cleared all my doubts for reversing a linked list recursively. Thanks for the video.
every one is asking how he is so enthusiastic but my mannnn took a preworkout and he is getting the pre workout kick!!!!
you're so good at explaining!. thanks !!
Thanks! try out the 5 day free mini course backtobackswe.com/
Finally a simple explanation. Thanking God for creating you 😁 😁 😁 😁 😁
Best video on recursion I have ever watched
I came here for the recursive method and the explanation was great! keep it up!
sure
Thnx! Finally, I got this logic of returning back after top to bottom😄
One of the more clear explanations of this god forsaken problem. Thank you
I watched so many explanations regarding this i could not understand but i got an idea about this by watching your video .
Kudos !!!
thanks
I love your enthusiasm. It makes it so much more fun to learn.
I thought the recursive way was really confusing so I had to look it up on TH-cam. Really glad I found this video. Amazing explanations!
haha nice, wassup
It took a while to sink in, but thanks for this detailed explanation to the problem. You killed it
thx
this is the best explanation of this concept
Hahaa yay
this is the best explanation for listNode reverse! Really appreciate it !!
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
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 😀
Best explanation out there
Thanks man
thanks
This guy is probably the most passionate CS guy in the entire universe!
Paid for a DSA course on Udemy and ended up have to TH-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
dude this guy is awesome i wish he was my professor
Absolutely the best video to explain this. Just took away all my frustration lol!!
Bro thanks alot man I final understand this stuff, thanks so much😭
Thanks buddy, I like your explanation better than other's.
nice
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 😀
Finally, I got it! Thank you so much for your video! Your channel is a hidden jam!
thanks!
Had to rewind a lot but first video that worked to understand it :)
i have seen many videos but urs is awesome and the best
thanks.
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
tysm man ...you literally nailed it with this explanation .....finally i understood how to do this now.
Oh your energy 🔥🔥🔥 I was going to sleep but now I will have a big brain time evening 😆😆😆 thanks so much!
Haha so glad!
Thanks, finally understand the recursive solution. The explanation of call stack really helps.
thanks
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 🍖
Thanks for the beautiful explanation
sure
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.
WAAAH I FINALLY UNDERSTAND IT BROO!!!
great
really love his way to explain this question🤣
he is so enthusiastic and energetic!
Watching your explanation and just the passion that you put into these videos really helped me remember the nuances of this problem.
great
Great explanation!!! gonna use your videos for interview prep. Many thanks 🙇
great!
THE BEST VIDEO ON TH-cam !!!!!!!! IM IN LOVE :)
omg you are a life savior
Sir the way you give so comprehensive explanation... I love it!
best explanation of reverse singly link list
Do you have any DSA course ?
How can someone thumbs down this video !!! Amazing effort and urge to explain the solution !!!
thanks
I got the logic by 3:20 you are really dope at this.
haha thx
Thanks for the video! You simplified this so much for me!
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/
You do a great job fam. Thousands of us appreciate the help. Thanks again
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.
love your videos, keep up the great work.
thanks
took me sometime for me to digest. thank you.
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
Love from India..🇮🇳🇮🇳
thanks
I really liked your explanation on the recursive method bro thanks
Awesome! One thing missing is head.next = null, because that link is not needed anymore.
My man big on energy. Love it!
Explanation is crystal damn clear.
thx
These videos are amazing. You're a phenomenal instructor.
Thanks man! subscribe to my DSA course for some amazing content b2bswe.co/3HhvIlV
Best explanation I have seen so far for reversing a singly linked list .
thx
Subscribed. Keep uploading videos like this everyday and your channel will grow a lot! You rock
Workin' on it. I'm tiring haha
@@BackToBackSWE Haha you can do it :) Thanks for your efforts!
I finally realize that how it works. Thank you man!
great to hear
Such a thorough and simple explanation. Thank you!
sure
Really love your illustration! Thank you!!
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 TH-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?
Life saver bro
Thanks for your kind explanation
This guy is something elese 🚀
Finally! A perfect explanation.
Best Explanation, thank you! I think you have to write the recursive version yourself and draw the nodes to really get it.
Yes
Great question and nice video. Simple, easy to understand tutorial with graphics and examples. Thanks!
love.