Reverse Linked List in Python
Learn how to reverse a linked list in Python! An easy, fun, beginner-friendly guide to solving this classic coding interview algorithm. Includes O(1) space iterative code.
Try it yourself
Run this code directly in your browser. Click "Open in full editor" to experiment further.
Click Run to see output
Or press Ctrl + Enter
How it works
Reversing a Linked List is an absolute legendary coding interview question. It looks simple at first glance, but it is the ultimate test of how well you understand pointers!
How It Works (The Iterative Approach)
Imagine you are walking down a line of people holding hands, pointing to the next person. To reverse the line, you just need them to let go and point to the person behind them instead!
But there's a massive trick: if they let go of the person in front of them, how do you know who is next in line? You'll lose the rest of the list into the void!
This is exactly why we need three "pointers" (think of them like sticky notes to remember who is who):
1. `prev`: The person behind us (initially nobody, so it's None).
2. `curr`: The person we are currently looking at.
3. `next_temp`: The person safely waiting in front of us.
The Magic Dance:
1. Save: Look at the person in front (next_temp = curr.next) so we don't lose the rest of the line!
2. Reverse: Tell the current person to turn around and point backwards to the person behind them! (curr.next = prev)
3. Move Forward: Step everyone forward one spot to repeat the process.
Time and Space Complexity
prev, curr, next_temp), no matter if the line has 10 people or a million people! It is super memory efficient.The Recursive Approach
You'll also see the Recursive version in our code. It is beautiful, elegant, and looks like magic. BUT, it requires O(n) space because the computer has to remember every single function call on its stack. The Iterative version is almost always preferred in the real world programming!
