Problem
Given the head of a singly linked list, reverse the list and return the reversed list's head.
Intuition — the key insight
Iteratively: maintain prev=null, curr=head. At each step, save curr.next, point curr.next to prev, move prev to curr, move curr to saved next. When curr is null, prev is the new head.
Approach
Iterative three-pointer
prev=None, curr=head. Loop: nextTemp=curr.next, curr.next=prev, prev=curr, curr=nextTemp. Return prev.
Complexity
Time
O(n)
Space
O(1)
Single pass. Three pointers — constant space.
Solution code
Python
def reverseList(self, head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prevEdge cases to remember
⚠Empty list: return null
⚠Single node: return as-is
Hints
What pattern do you think this problem uses?
Related problems
Progress is saved on this device