Plus One Linked List - CPP Solution

1. Introduction

This blog post addresses a unique challenge in linked list manipulation: incrementing a number represented by a singly linked list by one. This problem requires understanding linked list traversal, digit manipulation, and handling carryovers in arithmetic operations.

Problem

Given the head of a singly linked list representing a non-negative integer, where each node contains a single digit, the task is to add one to the number and return the resulting list. The most significant digit is at the head of the list.

2. Solution Steps

1. Reverse the linked list to simplify addition from the least significant digit.

2. Traverse the reversed list, adding one to the first node and handling carryovers.

3. Reverse the list again to restore the original order with the incremented value.

4. Handle edge cases like an empty list or a carryover after the last digit.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse a linked list
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head, *next = nullptr;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Function to add one to the linked list
ListNode* plusOne(ListNode* head) {
    if (!head) return new ListNode(1); // Handle empty list

    head = reverseList(head);
    ListNode *curr = head, *prev = nullptr;
    int carry = 1;

    while (curr) {
        int sum = curr->val + carry;
        curr->val = sum % 10;
        carry = sum / 10;
        prev = curr;
        curr = curr->next;
    }

    if (carry > 0) {
        prev->next = new ListNode(carry);
    }

    return reverseList(head);
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Creating a linked list representing the number 129
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(9);

    head = plusOne(head);
    printList(head); // Expected output: 1 -> 3 -> 0
    return 0;
}

Output:

1 -> 3 -> 0

Explanation:

The plusOne function first reverses the list to start addition from the least significant digit. 

It then traverses the list, adding one to the first node, and handles any carryover as it progresses through the list. After completing the addition, it reverses the list again to restore the original order with the incremented value. 

The function accounts for edge cases such as an empty list or a carryover after processing all digits, ensuring the correct representation of the incremented number.