🎨Now live: Try our Free AI Image Generation Feature

Description
The problem involves reversing a singly linked list. Given the head of a singly linked list, the task is to reverse the list and return the new head.
Intuition
To reverse the linked list, we can traverse through the list while adjusting the next
pointers of each node to point to its previous node. By maintaining pointers to the previous and current nodes, we can effectively reverse the direction of the list as we iterate through it.
Approach
- Edge Case: If the list is empty (i.e.,
head
isNone
), returnNone
immediately. - Initialization: Start with
prev
as the head of the list andcurr
as the second node (head.next
). - Iteration: Traverse the list using a
while
loop untilcurr
becomesNone
. During each iteration: - Store the next node temporarily (temp
). - Change thenext
pointer ofcurr
to point toprev
. - Moveprev
andcurr
one step forward. - Finalize: After the loop, set
head.next
toNone
to mark the end of the list, and returnprev
, which will now be the new head of the reversed list.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the linked list. Each node is visited exactly once.
Space Complexity:
O(1), as the reversal is done in-place without using any extra space except for a few pointers.
Code
C++
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
ListNode* prev = head;
ListNode* curr = head->next;
while (curr != nullptr) {
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
head->next = nullptr;
return prev;
}
};
Python
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
prev = head
curr = head.next
while curr is not None:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
head.next = None
return prev
Java
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return head;
ListNode prev = head;
ListNode curr = head.next;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head.next = null;
return prev;
}
}
JavaScript
var reverseList = function(head) {
if(head === null) return head;
let prev = head;
let curr = prev.next;
while(curr !== null){
let temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head.next = null
return prev;
};