Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list, and return the new head.

Input / Output Format

Input: Head of singly linked list. Output: Head of reversed linked 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: []

Approach Hints

• Iterative — Three pointers: prev = null, curr = head. Loop: save next = curr.next, set curr.next = prev, advance prev = curr, curr = next. Return prev. Time: O(n), Space: O(1).
• Recursive — reverse(head) returns new head; head.next.next = head; head.next = null. Time: O(n), Space: O(n) stack.
• Make sure not to lose the next pointer before reassigning.