Reverse Linked List
Problem
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: []
Key Insight
To reverse, change each node's `next` pointer to point to its previous node.
Save next, point current backward, advance. Repeat until end. Return prev as new head.
How to Approach This Problem
Pattern Recognition: When you see keywords like
reverse linked list linked-list,
think Linked List.
Step-by-Step Reasoning
1
To reverse a linked list, we change each node's:
Answer: next pointer
We don't change values or create nodes. We just redirect pointers.
2
After setting curr.next = prev, we lose:
Answer: Reference to the original next node
curr.next used to point forward. After changing it, we can't reach the rest of the list without saving it first.
3
To reverse iteratively, we need how many pointers?
Answer: 3
prev (new next), curr (current node), next_temp (saved forward reference).
4
At the start, prev should be:
Answer: null/None
After reversal, the original head becomes the tail, pointing to null.
5
We continue the loop while:
Answer: curr is not null
curr traverses each node. When curr is null, we've processed all nodes.
6
After the loop, we return:
Answer: prev (which is the new head)
prev ends up pointing to the last node we processed, which is the new head.
Solution
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next # Save next
curr.next = prev # Reverse pointer
prev = curr # Move prev forward
curr = next_temp # Move curr forward
return prevComplexity Analysis
| Time | O(n) |
|---|---|
| Space | O(1) |
Master This Pattern
Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.
Download LeetEye Free