# Reverse, plus one, then reverse

• easy understanding and fast

``````public class Solution {
ListNode dummy = new ListNode(0);
ListNode x = dummy;
int carry = 1;
while (carry > 0 || x.next != null) {
if (x.next != null) {
x = x.next;
carry += x.val;
x.val = carry % 10;
carry /= 10;
}
else {
x.next = new ListNode(carry);
x = x.next;
carry = 0;
}
}
return reverse(dummy.next);
}

ListNode tail = null;
}
return tail;
}
``````

}

• You are reversing the list twice and doing an additional pass to compute the result. Still `theta(n)` but it can be improved. You can do it in two passes (one forward to recurse till the end of the list, one backwards to modify the list till `head`). Check out my solution here, or @StefanPochmann's solution here.. He did it without the use of any helper function.

• I myself consider ours to take two passes, though, one forwards and one backwards.

• I actually thought about it too. I wanted to amend the post earlier but then started working. Will do it now.

• yeah, your code is clean and short. benefit of iterative way (by doing reverse) is that, space complexity is O(1), as no system stack used.

• @jiangbowei2010 Yeah, it's certainly better in that regard. My own first solution btw was iterative and O(1) as well, but the method had already been posted. So I just came up with something different to be worth posting. I should maybe try the double reverse method myself now.

• Ok I wrote my own (in Python) and it looks decent.

• Oh, just had another idea: reverse without helper function, and then a combined increase+reverse loop. Might be neat, too.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.