Given the head of a singly linked list representing a non-negative integer, add one to the number and return the updated linked list. The head node stores the most significant digit, and each node stores one digit.
Example 1
Input: head = [2, 3, 4]
Output: [2, 3, 5]
Explanation: Only the last digit changes because no carry moves left.
Example 2
Input: head = [9, 9, 9]
Output: [1, 0, 0, 0]
Explanation: Carry passes across every digit, so one extra head node is created.
Brute Force Approach
Forward-order storage makes the tail node the real starting point for addition, so recursion fits naturally. Recursive calls move to the end first, then the return path works like a backward traversal where carry travels from the last digit toward the head without reversing any pointers.
Algorithm
Use a recursive function to traverse the linked list until it reaches the end, as the digits are stored in forward order and the last digit needs to be processed first.
Return carry value
1from thenullbase case, since the required operation is to add1and the carry needs to begin from the least significant digit.During recursion unwind, add the received
carryto the current node's value, as the return path moves from the last digit toward the head.Store
sum % 10in the current node, since it represents the updated digit at the current position.Return
sum / 10as the next carry, allowing any overflow to move toward the more significant digit.After the top recursion call completes, create a new head node with value
1if the final carry is1, since this represents an additional most significant digit.Return the updated head after the entire linked list has been processed.
Dry Run
add one by recursion
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {private: // Propagate carry from tail to head through recursion. int addCarry(Node* head) { // Null node returns carry one for the initial plus-one operation. if (head == nullptr) { return 1; } // Recursively process the next node first. int carry = addCarry(head->next); // Add returned carry to the current digit. int sum = head->data + carry; // Store the updated digit. head->data = sum % 10; // Return carry for the previous node. return sum / 10; }public: // Function to add one to linked list. Node* addOne(Node* head) { // Collect carry after recursive processing finishes. int carry = addCarry(head); // Create a new head when carry remains after the top call. if (carry > 0) { Node* newHead = new Node(carry); newHead->next = head; return newHead; } // Return the original head when no extra node is required. return head; }};// Build a linked list from an array of digits.Node* buildList(const vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(Node* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the recursive solution on a hard-coded sample.int main() { vector<int> digits = {9, 9, 9}; Node* head = buildList(digits); Solution solution; Node* answer = solution.addOne(head); printList(answer); return 0;}Complexity Analysis
Time Complexity: O(N), one recursive traversal reaches every node once.
Space Complexity: O(N), recursion stack stores one call per node.
Optimal Approach
A very natural way to think about the number is from the last digit side because adding one always starts from the least significant digit. Since a singly linked list does not move backward, the list is first reversed, then one straight traversal handles carry from left to right in reversed order, and finally another reversal restores the original digit direction.
Algorithm
Reverse the linked list first, as adding
1starts from the least significant digit and reversing makes that digit directly accessible from the head.Initialize
carryas1, since the required operation is to add one to the number.Traverse the reversed list while a node exists and
carryis non-zero, as processing can stop once there is no carry left to propagate.Add
carryto the current node's value, storesum % 10in the node, and updatecarryusingsum / 10, since the remainder becomes the current digit while the quotient moves to the next position.Create an extra node with value
1at the tail ifcarryis still1after traversal, as this represents a new most significant digit, such as when the number consists entirely of9s.Reverse the linked list again, since the first reversal changed the digit order and the final result needs to follow the original forward direction.
Return the new head, which now represents the number after adding
1.
Dry Run
add one by reverse
Solution
#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {private: // Reverse a singly linked list and return the new head. Node* reverseList(Node* head) { // Previous pointer starts as null before reversal begins. Node* prev = nullptr; // Current pointer scans the original chain. Node* current = head; // Run one traversal and flip every next pointer. while (current != nullptr) { // Store the next node before pointer redirection. Node* front = current->next; // Reverse the current link. current->next = prev; // Shift both pointers forward. prev = current; current = front; } // Previous pointer becomes the new head. return prev; }public: // Add one to the linked-list number by reversing twice. Node* addOne(Node* head) { // Reverse the list so addition starts from the // least significant digit. head = reverseList(head); // Carry starts as one because the task adds one. int carry = 1; // Current pointer walks through the reversed list. Node* current = head; // Previous pointer helps in tail extension after traversal end. Node* prev = nullptr; // Continue while nodes remain and carry still needs propagation. while (current != nullptr && carry > 0) { // Add carry to the current digit. int sum = current->data + carry; // Store the updated digit. current->data = sum % 10; // Move carry to the next position. carry = sum / 10; // Move traversal pointers forward. prev = current; current = current->next; } // Attach one extra node when carry remains after the last node. if (carry > 0) { prev->next = new Node(carry); } // Reverse again to restore the original digit order. head = reverseList(head); // Return the updated head. return head; }};// Build a linked list from an array of digits.Node* buildList(const vector<int>& values) { Node* dummy = new Node(0); Node* tail = dummy; for (int value : values) { tail->next = new Node(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(Node* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the reverse-based solution on a hard-coded sample.int main() { vector<int> digits = {1, 5, 9}; Node* head = buildList(digits); Solution solution; Node* answer = solution.addOne(head);Complexity Analysis
Time Complexity: O(N), a constant number of full linked-list traversals are used.
Space Complexity: O(1), only pointer variables and one possible extra node are used.
Interview follow-up Questions
Reversal places the least significant digit at the head side, which makes carry propagation follow normal forward traversal.
Be the first to add a comment.