Linked List Reversal
Given the head of a singly linked list, reverse the list in place and
return the new head. You may not allocate a new list of nodes — you
must rewire the existing next pointers.
A singly linked list node looks like this:
Node
+------+------+
| val | next |---> (next node or None)
+------+------+
Example 1
Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
Output: 5 -> 4 -> 3 -> 2 -> 1 -> None
Example 2
Input: 1 -> 2 -> None
Output: 2 -> 1 -> None
Example 3
Input: None
Output: None
Constraints
- The number of nodes is in the range
[0, 5000]. -10^5 <= Node.val <= 10^5.- Solve it iteratively in O(1) extra space (a recursive O(n)-space solution is also acceptable as a follow-up discussion).
The core idea is to walk the list once while re-pointing each node's
next to the node that came before it, instead of the one that came
after. You need three references at every step: prev (the node you
just finished rewiring, initially None), curr (the node you're
currently rewiring), and next_node (a saved copy of curr.next,
captured before you overwrite curr.next, since that's the only way
to reach the rest of the list once the pointer is rewritten).
Each iteration does four things: save curr.next, point curr.next
back at prev, advance prev to curr, and advance curr to the
saved next_node. When curr becomes None, prev is sitting on
the last node visited — which is now the new head.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode | None) -> ListNode | None:
prev = None
curr = head
while curr is not None:
next_node = curr.next # save before overwriting
curr.next = prev # rewire backward
prev = curr # advance prev
curr = next_node # advance curr
return prev # prev is the new head
Complexity: O(n) time, since each node is visited and rewired exactly once. O(1) extra space, since only three pointer variables are used regardless of list length. A recursive version achieves the same time complexity but uses O(n) stack space.
Share this question