Reverse Linked List

Given the head of a singly linked list, reverse the list and return the new head. (Lists are shown as arrays: [1, 2, 3] is 1 → 2 → 3.)

Examples

Input:  head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Input:  head = []
Output: []

Constraints

• 0 ≤ number of nodes ≤ 5000

Explanation

Iterative — three pointers

Walk the list keeping prev (the already-reversed part) and cur. At each node: remember next = cur.next, point cur.next back to prev, then advance prev = cur, cur = next. When cur is null, prev is the new head.

null ← 1   2 → 3 → null      prev=1, cur=2
null ← 1 ← 2   3 → null      prev=2, cur=3
null ← 1 ← 2 ← 3             prev=3 (new head)

Recursive

Reverse the rest of the list, then make the next node point back: head.next.next = head; head.next = null. Elegant, but uses O(n) stack space.

Complexity

• Iterative: Time O(n), Space O(1).