Add one to linked list representation of an integer's digits

Question

I am trying to solve this challenge:

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

You may assume the integer does not contain any leading zero, except the number 0 itself.

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

Example:

Input: 1->2->3

Output: 1->2->4

This is my code:

class Solution
{
public:
    Node* addOne(Node *head) 
    {
        if (head == NULL)
        {
            return head;
        }
        Node* Temp = head;
        while (Temp->next != NULL)
        {
            Temp=Temp->next;
        }
        Temp->data = Temp->data+1;        
        return head;
    }
};

I submitted that code on LeetCode but it gives me an error and couldn't pass all test cases.

My code increments the last node's value by 1, but when that value was 9 the result is wrong. I don't see how I should turn that data into 0 and get a correct answer.

"I submit that code on leetcode": please provide the relevant link to the leetcode problem. — trincot
– trincot, Commented May 10, 2024 at 9:18

trincot · Accepted Answer · 2024-05-10 10:18:23Z

When the last digit is 9, you must apply the method that is taught in primary school: make that digit 0, and pass a carry of 1 to be added to the previous digit. If that previous digit is also 9, then repeat this procedure to the digits that precede it. In the ultimate case all digits happened to be 9, and after updating them all to 0, you need to prefix a new node before the list with the value of 1 (the carry).

Some examples of input and expected output:

input	expected output
1→2→3	1→2→4
1→2→9	1→3→0
1→9→9	2→0→0
9→9→9	1→0→0→0

In your approach you have lost the reference to the previous digit, so you cannot easily go back a node to apply the carry there. You can solve this in different ways. One is to write a recursive function that will add one to the remainder of the list (i.e. the nodes after the current node), and will report back whether there is a carry left over that must be applied to the current node.

Some other remarks on your code:

In C++ you should not use NULL, but nullptr. You can often even omit it, and just test the truthiness of a node reference.
Don't start variable names with a capital (Temp), but use camelCase. PascalCase (with an initial capital) is commonly used for the names of classes and interfaces, but not for local variables.

Here is an implementation:

class Solution
{
    bool addOneAndGetCarry(Node *head) {
        if (!head) {
            // At the end of the list we return a carry
            return true;
        }
        if (!addOneAndGetCarry(head->next)) {
            // If there is no carry we're done
            return false;
        }
        // Add the carry
        head->data = (head->data + 1) % 10;
        // Determine if we need to cascade a carry
        return head->data == 0;
    }
public:
    Node* addOne(Node *head) {
        if (addOneAndGetCarry(head)) { 
            // We have a carry: prefix digits with a new digit
            head = new Node(1, head);
        }
        return head;
    }
};

On a final node: the LeetCode problem 369 uses NodeList as type instead of Node, and has a val field instead of a data field. Before submitting, make sure you use their types and fields.

Collectives™ on Stack Overflow

Add one to linked list representation of an integer's digits

Example:

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example:

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related