247. Add 1 to a Number Represented as a Linked List

A non-negative integer is represented as a linked list of its n digits, most-significant digit first. Print the digits of that number plus 1, most-significant digit first, with no leading zeros.

Input: The first line contains an integer n, the number of digits. The second line contains n space-separated digits, most-significant digit first. Output: Print the resulting digits after adding 1, most-significant digit first, space-separated, with no leading zeros.

1 <= n <= 10^4

Recognizing this as a special case of 'Add Two Numbers Represented by Linked Lists' (rather than solving it from scratch) is a great example of noticing when a 'new-looking' problem is really a simpler instance of one you already know how to solve.

Given a number as a linked list of digits (most significant first), print the digits of that number plus 1. Brute force: Convert the entire linked list into an actual large integer, add 1 using built-in arithmetic, then convert back into a list of digits - this can work but may fail for extremely large numbers (up to 10^4 digits) exceeding standard integer type limits. Optimised: This is simply the 'Add Two Numbers' technique with the second 'number' fixed to be exactly 1 - processing from the least-significant digit and propagating carries handles numbers of ANY size correctly, with no dependency on a fixed-size integer type.

Reverse the linked list in place so the least significant digit becomes the head, then walk forward adding 1 with a carry that propagates node by node (a digit becomes (digit+1) mod 10, carrying 1 onward if it overflowed past 9) until the carry is absorbed or the list ends, appending one final node if a carry remains past the last digit. Finally reverse the list back to restore the original most-significant-digit-first order. This avoids the separate digit array of the brute-force approach, working entirely within the existing list's nodes. Time: O(n) Space: O(1)

Adding 1 only ever changes digits from the rightmost trailing run of 9s onward: scan forward once to find the rightmost node whose digit is not 9, increment that node's digit by 1, and set every node after it to 0 (since they were all 9s that roll over). If every digit in the list is a 9, prepend a brand-new head node with value 1 and zero out all existing nodes. This achieves the exact same result as reversing the list twice, but in a single forward pass with no reversal and no extra digit storage at all. Time: O(n) Space: O(1)

Traverse the linked list collecting its digits into an array or string (most significant digit first), treat that as a big-integer representation, add 1 to it using grade-school addition with carry propagation from the last digit backward, then build a brand-new linked list from the resulting digit sequence. This is easy to reason about since it mirrors how addition is normally taught, but it needs an entirely separate structure to hold the digits before rebuilding the list. Time: O(n) Space: O(n)

1. Reverse the digit list (or use a stack) so you can add 1 starting from the LEAST significant digit. 2. Add 1 to that first digit, propagating any carry to the next digit, and the next, and so on, exactly like manual addition. 3. If a carry survives past the very last (most-significant) digit, that adds ONE EXTRA leading digit to the result; reverse the result back to most-significant-first order before printing.

Time: O(n) - reversing and processing the digit list are both linear in the number of digits. Space: O(n) for the reversed/result digit sequence (or O(1) extra if reversing in place).

an all-9s input, where the carry propagates through every digit and adds one extra leading digit (e.g. 9 9 9 -> 1 0 0 0); n = 1 (a single digit, e.g. 9 becomes 1 0); n = 10^4 for performance.

Be ready to mention the classic '999 + 1 = 1000' edge case explicitly - a carry surviving past every existing digit requires adding one brand new leading digit to the result.