Turn the list around
EasyStuck?
Show a hintHide the hint
Keep three references: previous, current and the next one saved before you overwrite it. Point current back at previous and move all three along.
The ideas behind this problem
Next in this lesson
How deep does the tree goReverse a singly linked list and return the new head.
Worked example#
For 1 -> 2 -> 3 -> 4 -> 5, walk the list once, and as you pass each node point it back at the one before it.
Keep three references: the node before, the node you are on, and the node after.
| before | current | after | after the rewiring |
|---|---|---|---|
| null | 1 | 2 | 1 -> null |
| 1 | 2 | 3 | 2 -> 1 |
| 2 | 3 | 4 | 3 -> 2 |
| 3 | 4 | 5 | 4 -> 3 |
| 4 | 5 | null | 5 -> 4 |
When there is no current node left, before is the new head: 5.
The one thing to be careful about#
You must save current.next before you overwrite it. The moment you point the current node backwards, the rest of the list is unreachable through it, and if nothing else is holding that node you have lost everything after this point.
That is the whole difficulty of this problem, and it is why it is worth doing by hand on paper once.
The cost#
Time O(n), one pass. Memory O(1), because nothing is copied. That is the point of doing it by rewiring rather than reading the values into an array and building a new list.
Constraints#
0 <= number of nodes <= 5000-5000 <= value <= 5000- An empty list reverses to an empty list
Input
head is a count then that many values, in list order.
Output
The reversed list, values separated by spaces. An empty list prints an empty line.
Examples
Input
5 1 2 3 4 5
Output
5 4 3 2 1
Every link is turned around, so 5 becomes the head.
Input
2 1 2
Output
2 1
Two nodes simply swap places.
Input
0
Output
An empty list reverses to an empty list.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.