Plus One Linked List - Practice Coding Problems

Plus One Linked List - Problem

Given a non-negative integer represented as a linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

For example, the number 123 is stored as 1 → 2 → 3.

Goal: Add 1 to this number and return the modified linked list.

Input & Output

Example 1 — Basic Addition

$ Input: head = [1,2,3]

› Output: [1,2,4]

💡 Note: The number is 123, plus one gives 124, represented as 1→2→4

Example 2 — Carry Propagation

$ Input: head = [4,3,2,1]

› Output: [4,3,2,2]

💡 Note: The number is 4321, plus one gives 4322, represented as 4→3→2→2

Example 3 — All Nines

$ Input: head = [9,9,9]

› Output: [1,0,0,0]

💡 Note: The number is 999, plus one gives 1000, requiring a new head node: 1→0→0→0

Constraints

1 ≤ Number of nodes ≤ 100
0 ≤ Node.val ≤ 9
The number does not have leading zeros, except the number 0 itself

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list representing digits: 1→2→3 (number 123)

Process

Add 1 to the rightmost digit with carry propagation

Output

Modified linked list: 1→2→4 (number 124)

Key Takeaway

🎯 Key Insight: Use recursion to reach the rightmost digit first, then propagate carry back to handle the addition properly

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is handling carry propagation from right to left in a linked list. The recursive approach elegantly reaches the end first, then propagates carry back. Best approach: Recursive Carry - Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Carry	O(n)	O(n)	Use recursion to handle carry propagation from right to left
Convert to Integer	O(n)	O(n)	Convert linked list to integer, add 1, convert back to linked list

Recursive Carry — Algorithm Steps

Step 1: Recursively reach the end of the list
Step 2: Add 1 at the rightmost position and propagate carry back
Step 3: If carry remains, create new head with value 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Descent

Traverse to the rightmost digit

Add 1 and Propagate

Add 1 at the end, carry propagates back

Handle Final Carry

Create new head if carry remains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

int addCarry(struct ListNode* node) {
    if (!node) return 1; // Base case: add 1
    
    int carry = addCarry(node->next);
    int total = node->val + carry;
    node->val = total % 10;
    return total / 10;
}

struct ListNode* solution(struct ListNode* head) {
    if (!head) {
        struct ListNode* newNode = malloc(sizeof(struct ListNode));
        newNode->val = 1;
        newNode->next = NULL;
        return newNode;
    }
    
    int carry = addCarry(head);
    if (carry > 0) {
        struct ListNode* newHead = malloc(sizeof(struct ListNode));
        newHead->val = carry;
        newHead->next = head;
        return newHead;
    }
    
    return head;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[100];
    int size = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9') {
            arr[size++] = *ptr - '0';
        }
        ptr++;
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    // Print result
    printf("[");
    struct ListNode* current = result;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single recursive traversal through all nodes

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals length of linked list

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Carry — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler