Leetcode 369. Plus One Linked List

Problem Analysis

Given a singly linked list of digits representing a non-negative integer with the most significant digit at the head of the list. We are asked to plus one to the integer and return the new representation of the integer as a singly linked list.

For instance, if we have an integer 123 represented by the linked list [1,2,3], adding one to this integer gives 124 which is represented as [1,2,4] in the linked list.

To solve this problem, we need to traverse to the end of the linked list, add one to the last digit and manage any carry if it exists.

Solution Approach

We will solve this problem by using a recursive function that takes a node of the linked list, recursively reaches the end (most right node), adds one to the last digit and returns the carry.

Once it gets a carry from the recursive call, it adds the carry to the current node's value, returns the overflow as a new carry and leaves the value of the current node as the remainder of the sum divided by 10 (which is the remainder of the sum).

Let's illustrate this with an example, if we have a linked list represented by [1,9,9]. Our task is to add one to this integer which gives 200, represented by [2,0,0] in the linked list.

1
2
3Initial linked list :
4
51 -> 9 -> 9 
6
7After recursion and adding one to last digit :
8
91 -> 9 -> 0 (carry: 1)
10
11After managing the carry :
12
131 -> 0 -> 0 (carry: 1)
14
15Final state after managing the carry :
16
172 -> 0 -> 0

Solution

C++

1
2cpp
3class Solution {
4public:
5    ListNode* plusOne(ListNode* head) {
6        if (head == nullptr) return new ListNode(1);
7        if (addOne(head) == 1) return new ListNode(1, head);
8        return head;
9    }
10
11private:
12    int addOne(ListNode* node) {
13        // if node is most right one, add one and return carry
14        const int carry = node->next ? addOne(node->next) : 1;
15        // calculate sum with current value and carry
16        const int sum = node->val + carry;
17        node->val = sum % 10; // leave single digit in node's value
18        return sum / 10; // return overflow
19    }
20};

Python

1
2python
3class Solution:
4    def plusOne(self, head):
5        if not head: return ListNode(1)
6        carry = self.addOne(head)
7        if carry: return ListNode(carry, head)
8        return head
9
10    def addOne(self, node):
11        # if node is the most right node, add one and return carry
12        carry = self.addOne(node.next) if node.next else 1
13        # calculate sum with current value and carry
14        sum_value = node.val + carry
15        node.val = sum_value % 10  # leave single digit in node's value
16        return sum_value // 10  # return overflow

JavaScript

1
2js
3class Solution {
4    plusOne(head) {
5        if (!head) return new ListNode(1);
6        let carry = this.addOne(head)
7        if (carry) return new ListNode(carry, head);
8        return head;
9    }
10
11    addOne(node) {
12        // if node is the most right node, add one and return carry
13        let carry = node.next ? this.addOne(node.next) : 1;
14        // calculate sum with current value and carry
15        let sum = node.val + carry;
16        node.val = sum % 10;  // leave single digit in node's value
17        return Math.floor(sum / 10);  // return overflow
18    }
19}

Java

1
2java
3public class Solution {
4    public ListNode plusOne(ListNode head) {
5        if (head == null) return new ListNode(1);
6        if (addOne(head) == 1) {
7            ListNode newHead = new ListNode(1);
8            newHead.next = head;
9            return newHead;
10        }
11        return head;
12    }
13
14    private int addOne(ListNode node) {
15        // if node is the most right node, add one and return carry
16        int carry = node.next != null ? addOne(node.next) : 1;
17        // calculate sum with current value and carry
18        int sum = node.val + carry;
19        node.val = sum % 10; // leave single digit in node's value
20        return sum / 10; // return overflow
21    }
22}

C#

1
2csharp
3public class Solution {
4    public ListNode PlusOne(ListNode head) {
5        if (head == null) return new ListNode(1);
6        if (AddOne(head) == 1) {
7            ListNode newHead = new ListNode(1);
8            newHead.next = head;
9            return newHead;
10        }
11        return head;
12    }
13
14    private int AddOne(ListNode node) {
15        // if node is the most right one, add one and return carry
16        int carry = node.next != null ? AddOne(node.next) : 1;
17        // calculate sum with current value and carry
18        int sum = node.val + carry;
19        node.val = sum % 10; // leave single digit in node's value
20        return sum / 10; // return overflow
21    }
22}

Swift

1
2swift
3class ListNode {
4    var val: Int
5    var next: ListNode?
6    init(_ val: Int, _ next: ListNode? = nil) {
7        self.val = val
8        self.next = next
9    }
10}
11
12class Solution {
13    func plusOne(_ head: ListNode?) -> ListNode? {
14        if head == nil {
15            return ListNode(1)
16        }
17        let carry = addOne(head)
18        
19        if carry == 1 {
20            let newHead = ListNode(1)
21            newHead.next = head
22            return newHead
23        }
24        return head
25    }
26    
27    func addOne(node: ListNode?) -> Int {
28        if node == nil {
29            return 1
30        }
31        let carry = addOne(node: node?.next)
32        let sum = node!.val + carry
33        node!.val = sum % 10
34        return sum / 10
35    }
36}

Ruby

1
2ruby
3class ListNode
4    attr_accessor :val, :next
5    def initialize(val = 0, next_val = nil)
6       @val = val
7       @next = next_val
8    end
9end
10
11class Solution
12    def plus_one(head)
13        return ListNode.new(1) unless head
14        carry = add_one(head)
15        ((carry == 1) ? ListNode.new(1, head) : head)
16    end
17
18    def add_one(node)
19        return 1 unless node.next
20        carry = add_one(node.next) 
21        sum = node.val + carry
22        node.val = sum % 10
23        sum / 10
24    end
25end

Conclusion

The "Plus One" problem is common and understanding the recursive approach will help in solving similar problems related to linked lists, regardless of the programming language you use. Whether it's C++, Python, JavaScript, Java, C#, Swift or Ruby; the logic remains the same, it’s all about traversing to the rightmost node, adding one to it and handling any carry values appropriately.