Approach 1: Iterative (Long Code)
A two pointer approach can be employed to traverse the linked list and simultaneously reserving the pointers.
First of all, for corner cases viz. zero and one element return directly the head as the list contains less than two elements. Further, traverse the list with the help of two pointers, p and q, where p initially points to the first element and q points to the second element. At each step, we reverse the pointer between these two nodes q->next becomes p and then go to the next two nodes p becomes q and q becomes the next element.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL){
return head;
}
ListNode *p = head ,*q = head->next;
head->next = NULL;
while(q!=NULL){
ListNode *temp = q;
q = q->next;
temp->next = p;
p = temp;
}
return p;
}
};
Approach 2: Iterative (Short Code)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL;
while (head) {
ListNode* temp = head->next;
head->next = prev;
prev = head;
head = temp;
}
return prev;
}
};
Approach 3: Recursive
Recurse till the end of the list and return the last node. After each function call pop from the recursion stack, reverse the next pointer. See code below:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next)
return head;
ListNode* temp = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return temp;
}
}
Let's say the list is 1->2->3:
Recursion: reverseList(1) -> reverseList(2) -> reverseList(3)
reverseList(3) returns "3"
Then, in the function reverseList(2) function: head is 2. head->next is 3. So head->next->next = head implies 3->next = 2 hence reversing the arrow. head->next= NULL so 2->next = NULL. Now, our list is 1->2<-3
reverseList(2) returns "3" (temp)
Then, in the function reverseList(1): head is 1. head->next is 2. So head->next->next = head imples 2->next = 1 hence reversing the arrow. head->next = NULL implies 1->next = NULL. Now, our list is reversed! 1<-2<-3
reverseList(1) returns "3" (temp) which is the head of our new list.