Dare2Solve
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.
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.
head
is None
), return None
immediately.prev
as the head of the list and curr
as the second node (head.next
).while
loop until curr
becomes None
. During each iteration:
temp
).next
pointer of curr
to point to prev
.prev
and curr
one step forward.head.next
to None
to mark the end of the list, and return prev
, which will now be the new head of the reversed list.O(N), where N is the number of nodes in the linked list. Each node is visited exactly once.
O(1), as the reversal is done in-place without using any extra space except for a few pointers.
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;
}
};
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
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;
}
}
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;
};