Reverse Linked List
Given the `head` of a singly linked list, reverse the list in-place and return the new head (which was the old tail). **Core Insight:** We need to flip every `next` pointer so it points to the previous node instead of the next one. The trick is to keep track of three pointers simultaneously: `prev` (starts as null), `curr` (starts at head), and `next` (a temporary save of `curr.next` before we overwrite it). Each iteration we redirect `curr.next` to `prev`, then advance both pointers one step forward. **Algorithm:** Iterative three-pointer approach. At each step: save `next = curr.next`, set `curr.next = prev`, advance `prev = curr`, advance `curr = next`. When `curr` is null, `prev` is the new head. **Complexity:** Time O(n) — one pass through all n nodes. Space O(1) — only three pointer variables, no extra data structures.
Constraints
- •
The number of nodes is in the range [0, 5000] - •
-5000 ≤ Node.val ≤ 5000
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev