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:
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
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
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
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
Loop Ends
Now:
head = prev
So:
head = 40
Final Reversed List
40 → 30 → 20 → 10 → null
Comments
Post a Comment