Add One to a Number Represented as Linked List

A non-negative integer is stored as a singly linked list where the most significant digit is at the head and each node holds exactly one digit. Add 1 to the…

A non-negative integer is stored as a singly linked list where the most significant digit is at the head and each node holds exactly one digit. Add 1 to the number and return the resulting linked list in the same format (most significant digit at the head). For example, the list `1 → 2 → 3` represents 123. Adding 1 gives 124, so the result is `1 → 2 → 4`. The list `9 → 9 → 9` represents 999; adding 1 gives 1000, so a new node with value 1 must be prepended and the result is `1 → 0 → 0 → 0`.

- `1 <= number of nodes <= 10^5` - `0 <= node.val <= 9` - The represented number has no leading zeros (except the number 0 itself, which is a single node with value 0).

Example 1: input head = [1,2,3]; output [1,2,4]. 123 + 1 = 124. No carry past the last digit.

Example 2: input head = [1,2,9]; output [1,3,0]. 129 + 1 = 130. A carry propagates one step.

Example 3: input head = [9,9,9]; output [1,0,0,0]. 999 + 1 = 1000. All digits become 0 and a new leading 1 is prepended.

Category: Linked List. Topic: linked-list. Difficulty: Medium. Patterns: linked-list-traversal, in-place-reversal.