Reverse a Linked List
EasyGiven the head of a singly linked list, reverse the list, and return the reversed list.
Example
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation
To reverse a linked list, we can use an
iterative approach. We'll maintain three pointers: prev,
curr,
and next.
Initially, prev
will be None,
curr
will be the head of the list, and next
will be the next node of curr.
We'll iterate through the list, reversing the pointers as we go. In each iteration,
we'll update the next
pointer of curr
to point to prev,
then move prev
to curr
and curr
to next.
This process continues until curr
becomes None,
at which point prev
will be the new head of the reversed list.
Idea Map
Initialize prev = null, curr = head
Loop while curr != null
1. next_node = curr.next
2. curr.next = prev
3. prev = curr
4. curr = next_node
Return prev
Code
def reverseList(head):
Initializes the function `reverseList` which takes the head of the linked list as input.
prev = None
`prev` is initialized to `None`. This will eventually become the new head of the reversed list.
curr = head
`curr` is initialized to the current head of the list. We start traversing from here.
while curr:
The loop continues as long as `curr` is not `None`, meaning we haven't reached the end of the list.
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
1. `next_node` stores the next node in the original list.
2. `curr.next` is pointed to `prev`, reversing the link.
3. `prev` is moved to `curr`.
4. `curr` is moved to `next_node` to continue traversal.
return prev
Once the loop finishes, `prev` will be the new head of the reversed list.
public ListNode reverseList(ListNode head) {
Initializes the function `reverseList` which takes the head of the linked list as input.
ListNode prev = null;
`prev` is initialized to `null`. This will eventually become the new head of the reversed list.
ListNode curr = head;
`curr` is initialized to the current head of the list. We start traversing from here.
while (curr != null) {
The loop continues as long as `curr` is not `null`, meaning we haven't reached the end of the list.
ListNode next = curr.next;
Store the next node before we modify the current node's next pointer.
curr.next = prev;
Reverse the link by pointing current node's next to the previous node.
prev = curr;
Move `prev` to the current node for the next iteration.
curr = next;
Move `curr` to the next node to continue traversal.
}
End of the while loop.
return prev;
Once the loop finishes, `prev` will be the new head of the reversed list.
}
End of the function.
ListNode* reverseList(ListNode* head) {
Initializes the function `reverseList` which takes the head of the linked list as input.
ListNode* prev = nullptr;
`prev` is initialized to `nullptr`. This will eventually become the new head of the reversed list.
ListNode* curr = head;
`curr` is initialized to the current head of the list. We start traversing from here.
while (curr != nullptr) {
The loop continues as long as `curr` is not `nullptr`, meaning we haven't reached the end of the list.
ListNode* next = curr->next;
Store the next node before we modify the current node's next pointer.
curr->next = prev;
Reverse the link by pointing current node's next to the previous node.
prev = curr;
Move `prev` to the current node for the next iteration.
curr = next;
Move `curr` to the next node to continue traversal.
}
End of the while loop.
return prev;
Once the loop finishes, `prev` will be the new head of the reversed list.
}
End of the function.
What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes, and each node contains a value and a pointer to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for efficient insertion and deletion of elements.
Learn more about linked lists →Disclaimer: This problem is for educational purposes. We encourage you to try solving the 'Two Sum' question on LeetCode.