Optimal Iterative Approach & Code:
- Maintain three pointers (prev, curr, next_node) to reverse node pointers iteratively without extra memory.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
Complexity & Key Logic:
- Time Complexity: O(N) visiting each node exactly once.
- Space Complexity: O(1) auxiliary space modifying pointers in-place.
- Algorithm Details:
- Store the next node temporarily (next_node = curr.next) before breaking the link.
- Reverse the current node's pointer to point backward (curr.next = prev).
- Advance prev to curr, and curr to next_node.
- When curr reaches None, prev points to the new head of the reversed list.