Solution For Reverse Linked List
The Reverse Linked List problem on LeetCode is a popular problem that involves reversing the order of a singly linked list. This problem is rated as “Easy” difficulty on the LeetCode website and is a great problem for beginners to practice with.
The problem statement is as follows:
“Reverse a singly linked list.”
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
To solve this problem, we can use the iterative or the recursive approach. However, the iterative approach is more efficient and faster.
Iterative Solution
In the iterative solution, we need to traverse the linked list from the beginning and keep reversing the pointers until we reach the end of the list. We can maintain three pointers while traversing the list – current node, previous node, and next node.
Algorithm:
- Initialize previous node to NULL, current node to head, and next node to NULL.
- Traverse the linked list with the help of the current node.
- At each iteration, assign current->next = previous.
- Move to the next node with the help of the next pointer.
- Update previous node to the current node.
- Continue traversing the linked list until the current node is NULL.
- Return the new head, which is the previous node.
Code:
ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL, *current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
Time Complexity: O(n)
Space Complexity: O(1)
The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(1).
Recursive Solution
In the recursive solution, we reverse the list from the current node to the end of the list. Once we reach the end of the list, we update the pointer of the previous node to the current node.
Algorithm:
- If head is NULL or the list is empty, return head.
- Recursively reverse the rest of the list from the next node.
- Once we reach the end of the list, update the pointer for the previous node to the current node.
- Return the new head, which is the current node.
Code:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
Time Complexity: O(n)
Space Complexity: O(n)
The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(n) because we are using recursion. Each recursive call adds a new call frame to the call stack, which takes up space. This can lead to a stack overflow error for large input sizes.
Conclusion:
In conclusion, the Reverse Linked List problem is a great practice problem for beginners to get started with linked lists. The iterative solution is more efficient and faster since it has a space complexity of O(1). However, the recursive solution is also a good implementation to understand the concept of recursion.
Step by Step Implementation For Reverse Linked List
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { // if head is null or head.next is null, return head if (head == null || head.next == null) { return head; } // create a new node called prev and set it to null ListNode prev = null; // create a new node called curr and set it to head ListNode curr = head; // while curr is not null while (curr != null) { // create a new node called next and set it to curr.next ListNode next = curr.next; // set curr.next to prev curr.next = prev; // set prev to curr prev = curr; // set curr to next curr = next; } // return prev return prev; } }
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: # if head is None or head.next is None: # return head # # prev = None # curr = head # # while curr is not None: # next = curr.next # curr.next = prev # prev = curr # curr = next # # return prev # recursive solution if head is None or head.next is None: return head reversed_list = self.reverseList(head.next) head.next.next = head head.next = None return reversed_list
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { // if head is null or head.next is null, return head if (!head || !head.next) { return head; } // set up three pointers, prev, curr, and next let prev = null; let curr = head; let next = head.next; // while curr is not null while (curr) { // set curr.next to prev curr.next = prev; // move prev and curr pointers forward prev = curr; curr = next; // if next is not null, set next to next.next if (next) { next = next.next; } } // return prev which is now the new head return prev; };
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: //Recursive approach ListNode* reverseList(ListNode* head) { if(head == NULL || head->next == NULL) return head; ListNode* temp = reverseList(head->next); head->next->next = head; head->next = NULL; return temp; } };
//Given the head of a singly linked list, reverse it in-place. public class Solution { public ListNode ReverseList(ListNode head) { //edge case - if head is null, return null if(head == null) { return null; } //edge case - if head is the only node in the list, return head if(head.next == null) { return head; } //set up 3 pointers - prev, curr, and next ListNode prev = null; ListNode curr = head; ListNode next = null; //iterate through the list until curr is null while(curr != null) { //set next to be curr's next node next = curr.next; //set curr's next node to be prev curr.next = prev; //move prev and curr pointers forward prev = curr; curr = next; } //set head to be prev (which is now the last node in the list) head = prev; //return the new head of the list return head; } }