PPractick

The problem

A bank's legacy system stores account numbers too long for any integer type as linked lists of digits, most significant digit first, like 4 -> 5 -> 6 for 456. The "next account number" feature must add 1. The hard part is the carry: it starts at the last digit but the list only points forward, and a run of 9s like 9 -> 9 -> 9 turns into 1 -> 0 -> 0 -> 0, which needs a brand-new head node. Recursion handles it naturally: recurse to the tail, add the 1 there, and pass the carry back up as the calls return.

Example: 4 -> 5 -> 6 → 4 -> 5 -> 7; 9 -> 9 -> 9 → 1 -> 0 -> 0 -> 0.

Function signature

Node* addOne(Node* head);  // digits, most significant first; returns the (possibly new) head

Test cases

Input list	Output list	Explanation
4 -> 5 -> 6	4 -> 5 -> 7	No carry
1 -> 2 -> 9	1 -> 3 -> 0	A carry into the tens digit
9 -> 9 -> 9	1 -> 0 -> 0 -> 0	A new head is needed
0	1
9	1 -> 0

(Confirm: the list is non-empty with digits 0–9, most significant first, and no leading zeros except the number 0 itself.)

How interviewers phrase it

• "Add 1 to a number represented as a linked list" (GeeksforGeeks).
• Related: "plus one" on an array of digits (LeetCode 66), and "add two numbers II" where digits are most-significant first (LeetCode 445).

Clarifying questions to ask

1. Most significant digit first or last?
2. Can I modify the list in place?
3. Is recursion allowed? (The depth equals the number of digits.)

Follow-ups to expect

1. "How do you handle the carry without backward pointers?"
2. "When is a new node created?"
3. "Is there an O(1)-space, no-reversal trick?"
4. "Complexity?"

Related questions

• Add two numbers in Linked List Medium
• Find the repeating and missing number Medium
• Find square root of a number Medium
• Find Nth root of a number Medium
• Roman to Integer Medium
• String to Integer (atoi) Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in