In-place reversal of a Linked List
In this blog post, I will be giving a brief description about another data structure that is very important for technical interviews. This data structure is called in-place reversal of a linked list. This pattern is very useful to solve the problems that involves the reversal of a Linked List with the constraint that we need to do it in-place without using extra memory.
In this type of data structure pattern, we are going to reverse one node at a time. We will start with a variable current which will initially point to the head of the Linked List and a variable previous which will point to the previous node that we have processed; initially previous will point to null.
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.
How to identify if the problem uses this pattern?
If the question asks us to reverse the linked list without using extra memory.
Time Complexity: O(N) where N is the number of nodes in the Linked List
Space Complexity: O(1) , this means that the algorithm runs in a constant space
References:
