Visualizer › Linked List
Reverse a Linked List
Walks the list once with three pointers — prev, curr and next — and turns every next pointer around.
How it works
- Save next before changing curr.next, or you lose the rest of the list.
- At the end, prev is the new head.
- One of the most asked linked list interview questions.
Complexity
- Best time: O(n)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(1)
Code (Python)
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next # save the rest
curr.next = prev # turn the arrow
prev, curr = curr, nxt
return prev # new headPractise: Linked List problems