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:

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).
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.
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

[{"language":"Java","code":"public class Solution {\n    public class ListNode {\n        int val;\n        ListNode next;\n        ListNode(int x) { val = x; }\n    }\n\n    public ListNode plusOne(ListNode head) {\n        ListNode fakeHead = new ListNode(0);\n        fakeHead.next = head;\n        carry(fakeHead);\n        if (fakeHead.val != 0) {\n            return fakeHead;\n        }\n        return fakeHead.next;\n    }\n\n    private int carry(ListNode node) {\n        if (node == null) {\n            return 1;\n        }\n        int next = carry(node.next);\n        if (next == 0) {\n            return 0;\n        }\n        int tmp = node.val + next;\n        node.val = tmp % 10;\n        return tmp / 10;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> ListNode</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> val;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        ListNode next;</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">        ListNode</span><span style=\"color:#24292E

Related Tags