206. Reverse Linked List Leetcode Solution
Reverse Linked List Leetcode Problem :
Given the head of a singly linked list, reverse the list, and return the reversed list.
Reverse Linked List Leetcode Solution :
Constraints :
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
Example 1:
- Input: head = [1,2]
- Output: [2,1]
Example 2:
- Input: head = []
- Output: []
Intuition :
The problem is asking to reverse a singly-linked list. One common approach to reverse a linked list is to use recursion. The idea is to reverse the rest of the list and then move the current node to the end. The base case of the recursion is when the current node is null, in which case the head of the reversed list is set to the previous node.
Approach :
The solve function is a recursive function that reverses the linked list. It takes three parameters: head (a reference to the head of the reversed list), prev (the previous node in the reversed list), and curr (the current node in the original list).
- If curr is null, it means we have reached the end of the original list. In this case, we set the head to prev, effectively updating the head of the reversed list, and return.
- Otherwise, we store the next node in a variable (nextNode) to prevent losing the reference to the rest of the list.
- We make a recursive call to solve with updated parameters: head remains the same, curr becomes the next node (nextNode), and prev becomes the current node (curr).
- After the recursive call, we update the next pointer of the current node (curr->next) to point to the previous node (prev), effectively reversing the link.
The reverseList function is a wrapper function that checks if the list is empty or has only one element. If so, it returns the head unchanged. Otherwise, it calls the solve function to reverse the list and returns the updated head.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
void solve(ListNode* &head,ListNode* prev,ListNode* curr){
if(curr==NULL){
head=prev;
return;
}
ListNode* nextNode=curr->next;
solve(head,curr,nextNode);
curr->next=prev;
}
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL){
return head;
}
solve(head,NULL,head);
return head;
}
};
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode tmp = null;
while(curr != null)
{
tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
return prev;
}
}
def reverseList(self, head):
new_list = None
current = head
while current:
next_node = current.next
current.next = new_list
new_list = current
current = next_node
return new_list
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment