?????????????? ?? ?????????????????????

We have given the head of a singly linked list, reversed the list, and returned the reversed list.

Whenever I heard “Reverse” problem so, the solution that came to my mind is to use “Stack”. I know that the brute force approach and also takes O(n) extra space.

I hope you are able to identify the intuition behind why I’m using stack. If not go through the principle rule of the stack which is “LIFO” ( Last In First Out). due to its LIFO property, a stack is able to store elements in reverse order of their insertion and hence can be used to solve our problem.

So, how can we proceed further with this approach?:

1. Create an empty stack.
2. Iterate through the linked list and push the values of the nodes into the stack.
3. Now, after the iteration is complete, the linked list is stored in reverse order in the stack.
4. Now, start popping the elements from the stack and iterating through the linked list together, and change the values in the nodes by the values we get from the stack.
5. Finally, after the stack got empty, we will have the required reversed linked list.

Push Operation

Push node 1 in stack.

Push node 2 in stack.

Push node 3 in stack.

Now, curr.next == null so we are not going to add node 4 in our stack which is our last node. make That curr Node as “Head”.

Pop Operation

Makes our last node as “Head” node.

Pop node 3 from the stack, and curr.next = stack.pop(). And curr = curr.next.

Pop node 2 from the stack and do curr. next = stack.pop() ,and curr = curr.next.

Pop node 1 from the stack and do curr.next = stack.pop() , and curr = curr.next.

Now, the stack is empty then do curr.next =null.

Brute Force Code:

static Node reverseList(Node head) {

        Stack<Node> stack = new Stack<>();

        Node curr = head;
        while(curr.next != null){
            stack.push(curr);
            curr = curr.next;
        }

        head = curr;
        while(!stack.isEmpty()){
            curr.next = stack.peek();
            curr = curr.next;
            stack.pop();
        }

        curr.next = null;
        return head;

    }        

Time-Complexity — O(N)

Space-Complexity — O(N) , N is the number of Nodes in LinkedList.

Iterative Approach:

How can we optimize it much further, How to come up with an optimal solution in an Interview?

Here comes the Iterative Approach, Let’s talk about it.

The idea is to use three pointers?curr,?prev,?and temp to keep track of nodes to update reverse links.

How can we proceed further with this approach :

1. Initialize three pointers?prev?as NULL,?curr?as?head, and temp as NULL.
2. While traversing the list, we can change the current node’s next pointer to point to its previous element. Since a node does not have reference to its previous node, we must store its previous element beforehand. We also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

• Initialize three pointers?prev?as NULL,?curr?as?head, and temp as NULL.

• temp = curr.next , so we don’t wanna lose curr next link.

Now, point curr next to prev.

Update prev to curr.

Now update curr next to temp, where we have store curr.next previously.

And so on…..

Here is our final Linked List.

Code:

class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode prev = null;
        ListNode curr = head;
        ListNode temp = null;
        
        while(curr != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev;
    }
}        

Time-Complexity — O(N), N is the number of Nodes in LinkedList.

Space-Complexity — O(1)

Do Follow for More !!

LinkedIn: Santosh Kumar Mishra

Instagram: https://www.instagram.com/iamsantoshmishra

Subscribe to my YouTube channel: https://youtu.be/GP4k31mVcIg