[Interview Question] Reverse a Linked List
![*](https://i0.wp.com/allprowebdesigns.com/wp-content/uploads/2023/12/1703622701_maxresdefault.jpg?resize=840%2C430&ssl=1)
Video Title: [Interview Question] Reverse a Linked List
Reversing a linked list is one of those age-old questions that sometimes I feel like gets asked to every other interview or something slight exaggeration but anyway it’s such a good interview question because a very easily test whether you know what a linked list is and how to quickly manipulate the
Pointers in a linked list in addition it’s a really good question for the interviewer to ask for both iterative and recursive solutions to so they can also easily test whether you understand these two different programming styles and so just to refresh let’s look at what singly linked list is so a singly
Linked list is a list in which each node has one pointer a next pointer to the next node in the list so here we’ve got the first note to the second note there and so on you notice I also drew in this pointer from the last node to a box that just
Means null now if we want to reverse this list what we have to do is change these pointers so we’re going to want to make the last node point to the third node the third node point to the second node the second node point to the first
Node and here’s the the reason that I drew this null box in here we don’t want to forget to make the first node then point to no great so let’s do that iterative solution first and just sort of think about how we would do that looking at this picture so if we start
At the start node we’ll want to change the pointer from node 1 to point 2 null but as soon as we change this red arrow to be this blue arrow we will no longer be able to get to node 2 from node 1 so this immediately tells us that we’re
Going to want to save no to or the next node in the list as a variable now after we’ve changed so let me just erase this suppose we’ve seen no to so we can still get to know 2 and node 1 is now pointing to null now that
We’re at node 2 we want to change no twos pointer to point to node 1 but now we don’t have a reference to node 1 so that also tells us we need to save the previous node in the list and so that’s basically the basis for the iterative
Solution is we just iterate through the list and keep track of both the current node the next node and the previous node as we go so let’s code that up in my program so I wrote this quick list node class 2 it just has an item and then an
X pointer and uh yeah I’m using next as a variable but I’m not using any it’s like python iterators so that should be fine anyway so we start we’re passed in the start node and then we want to reverse everything so looking at this algorithm again we want to keep track of
The current so we’ll just assign current to be the start node we want to keep track of the previous node which is just going to be none for now and the next node which is also just nothing for now and then while we have the current node
Or while the current node exists and is not null then we want to go through the list so the first thing we want to do as you remember from what we did going through this list is we want to save that next node because we’re about to
Get rid of the pointer to it from the current node so next is equal to current dot next and then we want to change current to point to the previous and so this is why we start previous as none because we want the start node to point
To none after while we’re reversing it so current next is equal to previous and then we can simply increment previous and current there are the only other variables we haven’t incremented so previous sequel to current and then next is also going to be equal to current oh it sorry I
Meant to put current is equal to is equal to next here and then of course on the next iteration next will be updated again current will be update again I’m also gonna make our solutions to these returned the new starting node because obviously that would be useful in an
Actual solution so let’s return previous at the end of our solution ok great I wrote a quick script to test these so the iterative solution passes which is great and then the recursive one fails since we haven’t implemented it yet now let’s go ahead and think about how we
Would program the recursive solution so if we’re doing a recursive solution we basically we want to start by thinking of the base case maybe or that’s kind of like how I like to start thinking about recursive solutions to problems and if we think about what the base case would
Be in this list it would either be that there’s no next or that a node doesn’t exist anymore right which one you pick doesn’t really matter but since I want to kind of since I want to return the new starting node at the end it actually
Be easier for me to think of my base case as being one there’s no longer in next and this will be apparent when I actually code but so suppose we’re at the fourth note of this list and there’s no next here so this is kind of reaching
Our base case then we just want to return this node because I want to return the new start node and then after I’ve done that then I’m back to my next level up in the recursion and at node 3 what I would want to do is change the pointer from
From node 4 to point to node 3 so get rid of this red arrow and this and have it just point to the blue one and then I just basically want to keep doing that right and then after that I can maybe return this list and then I’m right here
And what I want to do is make node 3 point 2 Note 2 and so basically you’re always changing what so if this is the current you’re changing current dot next dot next right that’s kind of tricky it’s the next nodes next that you’re changing hopefully that kind of makes sense but
The idea is that we’re breaking the list into the first into the first element and then the rest of the list and then the first element the rest of the list first element the rest of the list and then recursing upwards from there so this let’s just do the solution and
Maybe I’ll be more clear so once again we have a start node so let’s call that like the first I guess or actually we don’t even need to give it a variable really so if start node dot next actually if if there isn’t a next which
Means we’re at the end of the list then let’s just return the start node because it’s gonna be the new start otherwise we’re going to recurse on the rest of the list and that’s going to give us the new start node since we’re returning that from our solution so new start is
Solution recursive start node dot next great and then after doing that we want to change this node change the pointer of the first noted the list we just returned and so that’s going to be start node dot next next remember is equal to the start node
And then launch or return and you start and so seems all good right almost so this works for note three this changes to point there I’m sorry for no two we change that to point to node one but there’s one thing we haven’t done and that’s set the first node to point to
Null and that’s kind of a tricky education that I think a lot of people will probably forget the first time they’re writing it but yeah so that leaves the edge case of changing the very first node in the list did point to null so we can simply change that by
Saying start node dot next is equal to none and this is fine because in all the previous recursion steps we just rewrote what that is right so every time we’re done with something really that arrow is always pointing to null but then we rewrite it into like an a blue arrow to
The previous node okay so let’s just that out yay both of them pass okay so hopefully you understand how to reverse a linked list both iteratively and recursively and you can just fly through that if you ever get asked from now on alright thanks for watching
-
Sale!
Wireless WIFI Repeater Extender Amplifier Booster 300Mbps
$29.99$14.99 Add to cartWireless WIFI Repeater Extender Amplifier Booster 300Mbps
Categories: Electronics, Wi-Fi Router, Wireless Wi-Fi Extender Tags: 300Mbps, 802.11N, Amplifier, Booster, Extender, mobile wi-fi booster, Remote, WIFI, Wireless, Wireless WIFI, Wireless WIFI Repeater, Wireless WIFI Repeater Extender, Wireless WIFI Repeater Extender Amplifier, Wireless WIFI Repeater Extender Amplifier Booster, Wireless WIFI Repeater Extender Amplifier Booster 300Mbps$29.99$14.99 -
Sale!
Full RGB Light Design Gaming Headset Headphones with Mic
$24.99$14.99 Add to cartFull RGB Light Design Gaming Headset Headphones with Mic
Categories: Electronics, Gaming, Gaming Headsets Tags: Design, Full, Full RGB Light Design Gaming Headset, Full RGB Light Design Gaming Headset Headphones, Full RGB Light Design Gaming Headset Headphones with Mic, Gamer, Gaming, Gaming Headset Headphones, gaming headset wireless, Headphone, Headphones, Headset, Light, Mic, Package, RGB$24.99$14.99 -
Sale!
Wireless BlueTooth Multi-Device Keyboard Mouse Combo
$39.99$19.99 Add to cartWireless BlueTooth Multi-Device Keyboard Mouse Combo
Categories: Electronics, Gaming, Gaming Keyboards, Keyboard Mouse Combos Tags: Combo, Keyboard, keyboard mouse combos, Mouse, MultiDevice, Set, WireKeyboard Mouse Combo, Wireless, Wireless BlueTooth Keyboard Mouse Combo, Wireless BlueTooth Keyboard Mouse Combos, Wireless BlueTooth Multi-Device Keyboard Mouse Combo, Wireless BlueTooth Multi-Device Keyboard Mouse Combos$39.99$19.99 -
Sale!
High Back Leather Executive Adjustable Swivel Gaming Chair with Headrest and Lumbar
$199.99$139.99 Add to cartHigh Back Leather Executive Adjustable Swivel Gaming Chair with Headrest and Lumbar
Categories: Gaming, Gaming Chairs Tags: Adjustable, Chair, computer chairs, Desk, Executive, Gaming, Girl, Headrest, High, High Back Leather Executive Adjustable Swivel Gaming Chair, High Back Leather Executive Adjustable Swivel Gaming Chair with Headrest, High Back Leather Executive Adjustable Swivel Gaming Chair with Headrest and Lumbar, High Back Leather Executive Adjustable Swivel Gaming Chairs, Leather, Lumbar, Office, Racing, Swivel$199.99$139.99 -
Sale!
Professional LED Light Wired Gaming Headphones with Noise Cancelling Microphone
$29.99$19.99 Select optionsProfessional LED Light Wired Gaming Headphones with Noise Cancelling Microphone
SKU: N/A Categories: Electronics, Gaming, Gaming Headsets Tags: Cancelling, Gaming, Gaming Headphones with Noise Cancelling Microphone, gaming headset, Headphones, Headset, LED, Light, Mic, Microphone, Noise, Professional, Professional LED Light Wired Gaming Headphones, Professional LED Light Wired Gaming Headphones with Noise Cancelling Microphone, Wired, Wired Gaming Headphones, Wired Gaming Headphones with Noise Cancelling Microphone$29.99$19.99 -
Sale!
Gaming Desk with LED Lights USB Power Outlets and Charging Ports
$349.99$249.99 Select optionsGaming Desk with LED Lights USB Power Outlets and Charging Ports
SKU: N/A Categories: Computer Desk, Gaming, Gaming Desk Tags: and Charging Ports, Charging, Desk, Desks, Gaming, gaming desk with led lights, Gaming Desks with LED Lights, Home, LED, Lights, Monitor, Office, Outlets, Port, Power, Room, Stand, USB, USB Power Outlets, White, Workstation$349.99$249.99 -
Sale!
Wired Mixed Backlit Anti-Ghosting Gaming Keyboard
$99.99$79.99 Add to cartWired Mixed Backlit Anti-Ghosting Gaming Keyboard
Categories: Electronics, Gaming, Gaming Keyboards Tags: Antighosting, Backlit, Blue, brown, Gaming, Gaming Keyboard, gaming keyboards, gaming keyboards and mouse, Keyboard, Laptop, Switch, Wired, Wired Mixed Backlit Anti-Ghosting Gaming Keyboard, Wired Mixed Backlit Anti-Ghosting Gaming Keyboards, Wired Mixed Backlit Gaming Keyboard$99.99$79.99 -
Sale!
Wireless Bluetooth 5.3 ANC Noise Cancellation Hi-Res Over the Ear Headphones Headset
$119.99$59.99 Add to cartWireless Bluetooth 5.3 ANC Noise Cancellation Hi-Res Over the Ear Headphones Headset
Categories: Electronics, Gaming, Gaming Headsets Tags: 5.3 ANC Noise Cancellation Hi-Res Over the Ear Headphones Headset, ANC, Audio, Bluetooth, Cancellation, Ear, Earphone, gaming headset, Headphones, Headset, Hi-Res Over the Ear Headphones Headset, HiRes, Noise, Wireless, Wireless Bluetooth 5.3 ANC Noise Cancellation Hi-Res Headphones, Wireless Bluetooth 5.3 ANC Noise Cancellation Hi-Res Over the Ear Headphones Headset, Wireless Bluetooth 5.3 ANC Noise Cancellation Hi-Res Over the Ear Headphones Headsets$119.99$59.99 -
Sale!
Wired Sports Gaming Headset Earbuds with Microphone
$19.99$9.99 Select optionsWired Sports Gaming Headset Earbuds with Microphone
SKU: N/A Categories: Gaming, Gaming Headsets Tags: Accessories, Earbud, Earphone, Earphones, Gaming, gaming headset with microphone, Headphones, Headset, IOS, Microphone, Sports, Wired, Wired Sports Gaming Headset Earbuds, Wired Sports Gaming Headset Earbuds with Microphone, Wired Sports Headset Earbuds$19.99$9.99 -
Sale!
150W Universal Multi USB Fast Charger 16 Port MAX Charging Station
$49.99$29.99 Add to cart150W Universal Multi USB Fast Charger 16 Port MAX Charging Station
Categories: Charging Stations, Electronics Tags: 150W, 150W Charging Station, 150W Universal Multi USB Charging Station, 150W Universal Multi USB Fast Charger 16 Port MAX Charging Station, 150W Universal Multi USB Fast Charger 16 Port MAX Charging Stations, 150W Universal Multi USB MAX Charging Station, 16 Port MAX Charging Station, 3.5A, Charger, Charging, Fast, laptop charging stations, Max, Multi, Port, Stand, Station, Universal, USB$49.99$29.99
The Khan Academy of coding interview questions
I cant listen this voice, it's like Donald duck
Very cool, what kind of program do you use to do your diagrams?
Very helpful!
i do not understand the recursive one.. watched like 7 times >:(
And the award for the shittiest voice on YouTube goes to…
This is very good. I must have tried at least five other videos and they overcomplicated it. With this I was able to get it even though I'm working in Java and your solution is in Python. Thank you.
This was really helpful. Thanks!
your voice is literally the female version of ike haxton's
Agree, to the very top in the recursive function:
if not start_node:
return
Hi, Smitha! Thank you so much for the video. Could you please explain why ' return Prev ' at last?
thanks for sharing that, keep working on it girl.
Thank you! Nice and simple explanation.
good stuff.
In recursive part, I would add this on the very top
if not start_node:
return None
just in case start_node is NULL
After watching/reading other tutorials, your is the first one that actually makes sense!!!