Description
Given the head of a singly linked list, reverse the list, and return the reversed list.
Examples:
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []Solution in Python
Python
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Initialize three pointers:
prev = None # This will eventually become the new head of the reversed list
current = head # Start with the current node as the head of the original list
while current:
# Save the next node before changing the link
next_node = current.next # Store the next node
# Reverse the link
current.next = prev # Make the current node point to the previous node
# Move the pointers one position forward
prev = current # Move prev to the current node
current = next_node # Move current to the next node (original next node)
# At the end of the loop, prev will be pointing to the new head of the reversed list
return prev # Return the new head of the reversed listExplanation:
- Initialization:
previs initialized toNone. This will eventually become the new head of the reversed list.currentis initialized tohead, which is the current node we’re processing.
- Loop through the list:
- The
while current:loop continues as long as there are nodes to process. next_nodestores the next node in the original list to prevent losing track of the remaining list when reversing the link.current.next = prevreverses the link by making the current node point to the previous node.prevandcurrentare then moved forward to continue reversing the next node in the list.
- The
- Return the new head:
- After the loop ends,
prevwill be pointing to the new head of the reversed list. - We return
prevas the head of the reversed list.
- After the loop ends,
This function effectively reverses the singly linked list in place, using constant space.
Solution in Javascript
JavaScript
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
// Initialize three pointers:
let prev = null; // This will eventually become the new head of the reversed list
let current = head; // Start with the current node as the head of the original list
while (current !== null) {
// Save the next node before changing the link
let nextNode = current.next; // Store the next node
// Reverse the link
current.next = prev; // Make the current node point to the previous node
// Move the pointers one position forward
prev = current; // Move prev to the current node
current = nextNode; // Move current to the next node (original next node)
}
// At the end of the loop, prev will be pointing to the new head of the reversed list
return prev; // Return the new head of the reversed list
};Solution in Java
Java
class Solution {
public ListNode reverseList(ListNode head) {
// Initialize three pointers:
ListNode prev = null; // This will eventually become the new head of the reversed list
ListNode current = head; // Start with the current node as the head of the original list
while (current != null) {
// Save the next node before changing the link
ListNode nextNode = current.next; // Store the next node
// Reverse the link
current.next = prev; // Make the current node point to the previous node
// Move the pointers one position forward
prev = current; // Move prev to the current node
current = nextNode; // Move current to the next node (original next node)
}
// At the end of the loop, prev will be pointing to the new head of the reversed list
return prev; // Return the new head of the reversed list
}
}Solution in C#
C#
public class Solution {
public ListNode ReverseList(ListNode head) {
// Initialize two pointers:
ListNode prev = null; // This will eventually become the new head of the reversed list
ListNode current = head; // Start with the current node as the head of the original list
while (current != null) {
// Save the next node before changing the link
ListNode nextNode = current.next; // Store the next node
// Reverse the link
current.next = prev; // Make the current node point to the previous node
// Move the pointers one position forward
prev = current; // Move prev to the current node
current = nextNode; // Move current to the next node (original next node)
}
// At the end of the loop, prev will be pointing to the new head of the reversed list
return prev; // Return the new head of the reversed list
}
}