Increment a Number Represented as a Linked List

You are given a non-negative integer represented as a singly linked list where each node contains a single digit. The digits are stored in forward order, i.e. the head node contains the most significant digit. Your task is to add one to the number and return the resulting linked list.

For example, if the input linked list is 1 → 2 → 3, it represents the number \(123\). After adding one, the number becomes \(124\) and the new linked list should be 1 → 2 → 4. Similarly, when the input is 9 → 9 → 9 representing \(999\), the output should be 1 → 0 → 0 → 0 because the addition results in a carry that increases the number of digits.

Note: If the input linked list is empty (i.e. has 0 nodes), output nothing.

inputFormat

The first line of input contains a single integer \(n\) representing the number of nodes in the linked list. The second line contains \(n\) space-separated digits representing the number from the most significant digit to the least significant digit. If \(n = 0\), the list is empty.

outputFormat

Output the digits of the new linked list after adding one, separated by a single space. There should be no extra spaces at the end of the output.

3
1 2 3

1 2 4