206. Reverse Linked List
On This Page
Reverse a given singly linked list and return its head. A singly linked list is a data structure consisting of nodes, where each node has a value and a reference to the next node in the sequence.
A naive approach could be to traverse the entire linked list once to read all its elements into an array. Then, we could reverse the array and construct a new linked list from it. This would work, but it takes up additional space for the array.
Hints & Tips
An efficient way to approach this problem is by using pointers to reverse the links between the nodes directly within the linked list, without using additional space.
We will discuss two approaches to solve this problem: Iterative and Recursive.
- Initialize three pointers:
currentas the head of the linked list, and
- Traverse the linked list, reversing the
nextpointers of each node to point to its previous node.
prev = Noneand
current = head.
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev = None curr = head while curr: next = curr.next curr.next = prev prev = curr curr = next return prev
- Traverse to the end of the list.
- As the recursion stack unwinds, change the
nextpointers to create the reversed list.
- Base case: If the
- Recursively reverse the rest of the list.
- Change the next-next pointer to reverse the list.
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head