Problem Statement
Given the head of a Singly LinkedList, reverse the LinkedList. Write a function to return the new head of the reversed LinkedList.
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Why this is an In-place Reversal of a Linked List problem
| What the question says | The signal it matches |
|---|---|
| "Given the head of a Singly LinkedList, reverse the LinkedList" | the input is a linked list and the wording says reverse |
| "return the new head of the reversed LinkedList" | the links themselves change, not a copy of the values |
| reading the values out and rebuilding the list backwards | your first idea is to copy the values into an array |
Flipping every link in one pass is the reverse everything variant.
The closest alternative. Copy the values into an array, reverse it, and write them back. That is correct and easier to write. It costs O(N) memory.
This chapter is about doing it with three pointers and no extra memory. Expect that to be asked for even when the question does not say so.
Solution
To reverse a LinkedList, we need to reverse one node at a time. We will start with a variable current which will initially point to the head of the LinkedList and a variable previous which will point to the previous node that we have processed; initially previous will point to null.
In a stepwise manner, we will reverse the current node by pointing it to the previous before moving on to the next node. Also, we will update the previous to always point to the previous node that we have processed. Here is the visual representation of our algorithm:
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.
Space Complexity
We only used constant space, therefore, the space complexity of our algorithm is O(1).