Reverse, plus one, then reverse


  • 2
    J

    easy understanding and fast

    public class Solution {
        public ListNode plusOne(ListNode head) {
            head = reverse(head);
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            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);
        }
        
        private ListNode reverse(ListNode head) {
            ListNode tail = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = tail;
                tail = head;
                head = temp;
            }
            return tail;
        }
    

    }


  • 0

    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.


  • 0

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


  • 0

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


  • 0
    J

    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.


  • 0

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


  • 0

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


  • 0

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


Log in to reply
 

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