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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.