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.

Examples

Example 1:

1
2

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

Solution

Method 1 - Iterative with Reverse

To add one to a non-negative number represented as a singly linked list of digits, starting from the most significant digit:

  1. Reverse the Linked List: By reversing the list, we can easily add one to the number starting from the least significant digit, which is now the head of the reversed list.
  2. Add One: Traverse the reversed list, add one to the first node, and handle the carry if required.
  3. Reverse Again: Reverse the list again to restore the original order with the updated digits.

Here is the approach:

  1. Reverse the Linked List: Utilize a helper function to reverse the linked list.
  2. Add One:
    • Traverse the reversed list and add one to the node’s value.
    • Handle the carry: if a node becomes 10, set its value to 0 and carry the one to the next node.
    • If the carry persists after the last node, append a new node with value 1.
  3. Reverse the Linked List Again to restore the original order.

Code

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
	public ListNode plusOne(ListNode head) {
		ListNode h2 = reverse(head);
	
		ListNode curr = h2;
		int carry = 1;
	
		while (curr != null) {
			int sum = curr.val + carry;
            curr.val = sum % 10;
            carry = sum / 10;
 
            if (carry == 0) {
                break;
            }
 
            if (curr.next == null && carry == 1) {
                node.next = new ListNode(1);
                carry = 0;
            }
            curr = curr.next;			
		}
	
		return reverse(h2);
	}
	
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def plusOne(self, head: Optional['Solution.ListNode']) -> Optional['Solution.ListNode']:
        head = self.reverse(head)
        node = head
        carry = 1

        while node:
            sum_val = node.val + carry
            node.val = sum_val % 10
            carry = sum_val // 10

            if carry == 0:
                break

            if node.next is None and carry == 1:
                node.next = Solution.ListNode(1)
                carry = 0
            node = node.next

        return self.reverse(head)

    def reverse(self, head: Optional['Solution.ListNode']) -> Optional['Solution.ListNode']:
        prev = None
        while head:
            next_node = head.next
            head.next = prev
            prev = head
            head = next_node
        return prev

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list, as each step (reversing the list, adding one, and reversing the list again) takes O(n) time.
  • 🧺 Space complexity: O(1)

Method 2 - Recursive

A recursive approach can also be used to add one to a number represented as a singly linked list. By traversing the linked list to the very end and then adding one, we can handle the carry recursively while returning to the head of the list.

Here is the approach:

  1. Add a Fake Head: Create a dummy node before the actual head to handle cases where an additional digit is required (e.g., 999 + 1 = 1000).
  2. Recursive Carry Function: Define a recursive function that traverses to the end of the list.
    • If the node is null, return a carry of 1.
    • Recursively call the carry function for the next node.
    • Add the carry to the current node’s value and update the node’s value.
    • Return the carry obtained from the current addition.
  3. Return Result: After handling the carry, check if the dummy node’s value is non-zero. If so, return the dummy node; otherwise, return the original head.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode plusOne(ListNode head) {
        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;
        carry(fakeHead);
        if (fakeHead.val != 0) {
            return fakeHead;
        }
        return fakeHead.next;
    }

    private int carry(ListNode node) {
        if (node == null) {
            return 1;
        }
        int next = carry(node.next);
        if (next == 0) {
            return 0;
        }
        int tmp = node.val + next;
        node.val = tmp % 10;
        return tmp / 10;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def plusOne(self, head: Optional['Solution.ListNode']) -> Optional['Solution.ListNode']:
        fake_head = self.ListNode(0)
        fake_head.next = head
        self.carry(fake_head)
        if fake_head.val != 0:
            return fake_head
        return fake_head.next

    def carry(self, node: Optional['Solution.ListNode']) -> int:
        if node is None:
            return 1
        next_carry = self.carry(node.next)
        if next_carry == 0:
            return 0
        temp = node.val + next_carry
        node.val = temp % 10
        return temp // 10

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes, as each node is visited once.
  • 🧺 Space complexity: O(n) due to the recursive call stack.