Difficulty : Easy
Question : Given the head of a singly linked list, reverse the list, and return the reversed list.
Example :
Input : head = [1,2,3,4,5]
Output : [5,4,3,2,1]
Solution :
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* curr;
ListNode*prev;
prev=NULL;
curr=head;
while(curr!=NULL){
ListNode* temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
return prev;
}
};
Language - C++
Explanation -
Reversing a linked list is straightforward! We'll use two pointers, curr
and prev
, both of ListNode
type. Initially, prev
points to NULL
and curr
points to head
.
Now, let's understand the process through an example:
Suppose the linked list is 2 -> 3 -> 5
.
- Initially:
curr
is2
prev
isNULL
We begin a while
loop where we'll make another pointer temp
point to curr->next
. Let’s walk through each iteration:
- Before the loop body:
curr
= 2prev
= NULLhead
= 2 -> 3 -> 5
-
temp = curr->next
:temp
now points to3
-
curr->next = prev
:- The next pointer of
curr
(2) now points toNULL
- Updated list:
2 -> NULL
- The next pointer of
-
prev = curr
:prev
now points to2
-
curr = temp
:curr
now points to3
- Before the loop body:
curr
= 3prev
= 2head
= 2 -> NULL
-
temp = curr->next
:temp
now points to5
-
curr->next = prev
:- The next pointer of
curr
(3) now points to2
- Updated list:
3 -> 2 -> NULL
- The next pointer of
-
prev = curr
:prev
now points to3
-
curr = temp
:curr
now points to5
- Before the loop body:
curr
= 5prev
= 3head
= 2 -> NULL
-
temp = curr->next
:temp
now points toNULL
-
curr->next = prev
:- The next pointer of
curr
(5) now points to3
- Updated list:
5 -> 3 -> 2 -> NULL
- The next pointer of
-
prev = curr
:prev
now points to5
-
curr = temp
:curr
now points toNULL
Now curr
is NULL
, so the while
loop stops.
The pointer prev
now points to the reversed linked list: 5 -> 3 -> 2 -> NULL
.
And there you have it! You've successfully reversed the linked list.