324. Add 1 to a Number Represented as Linked List

A non-negative integer is represented as a linked list of digits (head = most significant digit). Add 1 to this number and return the head of the result.

Handle carry propagation correctly. If a new digit is needed (e.g., 999→1000), prepend a new node.

Input: Head of a linked list where each node contains a single digit [0-9]. Head = most significant digit.

Output: Head of the resulting linked list after adding 1.

Examples

Input: [1,2,3]
Output: [1,2,4]
Explanation: 123 + 1 = 124. Last digit 3+1=4, no carry.

Input: [9,9,9]
Output: [1,0,0,0]
Explanation: 999 + 1 = 1000. Carry propagates through all digits. New head node with value 1.

Input: [1,9,9]
Output: [2,0,0]
Explanation: 199 + 1 = 200. Carry from 9→9→1.

Constraints

• 1<=nodes<=100
• 0<=Node.val<=9
• No leading zeros except single 0

Asked by