Problem Statement:
Given the head of a singly linked list, reverse the list, and return the reversed list.
Examples:
- Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1] - Input: head = [1,2]
Output: [2,1] - Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range [0, 5000].
- -5000 ≤ Node.val ≤ 5000
Approach:
- Use three pointers:
prev,curr, andtemp. - In each step:
- Save the next node.
- Point current node’s
nextto previous. - Move
prevandcurrforward.
- Return
prevas the new head.
Time and Space Complexity:
- Time Complexity: O(n), where n is the number of nodes in the list. We visit each node once.
- Space Complexity: O(1), since we reverse the list in-place using a constant number of pointers.
var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr) {
let temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
};
class Solution:
def reverseList(self, head):
prev = None
curr = head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
