Reverse Linked List

Reverse a Singly Linked List Objective :-
Given the head of a singly linked list, reverse the list so that:
The first node becomes the last

The last node becomes the first

All next pointers are reversed

The operation is done in-place

Return the new head of the reversed list.
Understanding the Problem
A singly linked list is a sequence of nodes where each node contains:
A value

A reference to the next node

Example:
1 → 2 → 3 → 4 → null
After reversing:
4 → 3 → 2 → 1 → null

Intuition
Here is how the linked list looks like.

We are given a “head”. Which is pointing to the first node. (Node stores the value and the address to the next node.)

So, What we can do here is if we store the next node’s address to the previous one then we can reverse the Linked List.

In Linked List each node points to the next node so we traverse in the List and swap the address to pointing backward then maybe we reverse the LL.

Let’s Try…

So we required two pointers that help us to do that. Let’s take “previous” and “current” two pointers to help us.

Now if you think we can assign previous to the head and current to the next of head then just we have to swap the address but be careful first store the current.next into temp node so you can go to the next address otherwise the next will be gone.
Approach
Here how each steps looks like:
Step 1:

Prev = 100, curr = 200.
temp = curr.next (300) //store the next of current
curr.next = prev (100) //store the previous address to the current’s next.
prev = curr (200) // move prev to the current
curr = temp (300) //move the current to the next address.

Step 2:

Prev = 200, curr = 300.
temp = curr.next (400) //store the next of current
curr.next = prev (200) //store the previous address to the current’s next.
prev = curr (300) // move prev to the current
curr = temp (400) //move the current to the next address.

Step 3:

Prev = 300, curr = 400.
temp = curr.next (null) //store the next of current
curr.next = prev (300) //store the previous address to the current’s next.
prev = curr (400) // move prev to the current
curr = temp (null) //move the current to the next address.

Step 4:

At Last, Curr stores the null and prev is on the last Node.

head.next = curr (null)
head = prev;

Final Output:

But there are some flows in this approach: what if the head or next of head is null? Also we will update the head node’s address at the end. That also makes it a more complicated approach it works fine although if you just handle the null pointer cases.

But if we take the current as head and prev as null and follow the same logic that is more appropriate and more intuitive.
Code Solution:

void reverseLL() {
LinkedNode prev = null;
LinkedNode current = head;

while (current != null){
LinkedNode next = current.next; // store the current node's next address
current.next = prev; // now store the previous address to the current node's address
prev = current; // update the previous with current one
current = next; // move current to the next location
}

//At the end Prev pointing to the last node
head = prev;
}

Initial State Before Loop:
Variable
Value
prev
null
current
10
head
10

Iteration 1
Step 1
next = current.next → 20
Step 2
current.next = prev
10 → null
Step 3
prev = current → 10
Step 4
current = next → 20

State After Iteration 1
Reversed part:
10 → null
Remaining:
20 → 30 → 40 → null
prev
current
next
10
20
20

Iteration 2
Step 1
next = 30
Step 2
20.next = 10
Step 3
prev = 20
Step 4
current = 30

State After Iteration 2
Reversed part:
20 → 10 → null
Remaining:
30 → 40 → null
prev
current
20
30

Iteration 3
Step 1
next = 40
Step 2
30.next = 20
Step 3
prev = 30
Step 4
current = 40

State After Iteration 3
Reversed part:
30 → 20 → 10 → null
Remaining:
40 → null
prev
current
30
40

Iteration 4
Step 1
next = null
Step 2
40.next = 30
Step 3
prev = 40
Step 4
current = null

State After Iteration 4
Reversed part:
40 → 30 → 20 → 10 → null
Remaining:
null
prev
current
40
null

Loop Ends
Now:
head = prev
So:
head = 40

Final Reversed List
40 → 30 → 20 → 10 → null