Iterative Two-Pointers with dummy node Java O(n) time, O(1) space


  • 85
    public class Solution {
        public ListNode plusOne(ListNode head) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode i = dummy;
            ListNode j = dummy;
            
            while (j.next != null) {
                j = j.next;
                if (j.val != 9) {
                    i = j;
                }
            }
            
            if (j.val != 9) {
                j.val++;
            } else {
                i.val++;
                i = i.next;
                while (i != null) {
                    i.val = 0;
                    i = i.next;
                }
            }
            
            if (dummy.val == 0) {
                return dummy.next;
            }
            
            return dummy;
        }
    }
    
    • i stands for the most significant digit that is going to be incremented if there exists a carry
    • dummy node can handle cases such as "9->9>-9" automatically

  • 50
    H

    Nice solution. Simplified a little bit.

    public class Solution {
        public ListNode plusOne(ListNode head) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode lastNotNine = dummy, node = head;
            
            while (node != null) {
                if (node.val != 9) {
                    lastNotNine = node;
                }
                node = node.next;
            }
            lastNotNine.val++;
            node = lastNotNine.next;
            while (node != null) {
                node.val = 0;
                node = node.next;
            }
            return dummy.val == 1 ? dummy : dummy.next;
        }
    }
    

  • 0
    K
    This post is deleted!

  • 8
    R

    Good solution. Try to explain with example 1->8->9->7->9->9.
    Pointer i points to the first node before the tailing 9s, which is 7 in this case and pointer j points to the last node of the whole list, which is 9.

    1. If the value of j equals to 9, the sublist behind i should be updated. Increments the value of 1 by 1 and set the following nodes to be 0.
    2. If the value of j is not 9, just increments j.val by one.

    The use of dummy node:

    1. In the cases like 9->9->9, the answer should return dummy. (1->0->0->0)
    2. In other cases like 8->9->9, the answer should return dummy.next. (0->9->0->0, dummy is the first 0).

  • 0
    I

    @ocean you don't need j, i is enough. When "if (j.val != 9) ", i is equal to j.


  • 3

    Very nice solution. Especially the use of dummy head.
    Note the invariant which help we think and code correctly. Thanks for sharing!

        public ListNode plusOne(ListNode head) {
            ListNode dmy = new ListNode(0), lastNot9 = dmy;
            dmy.next = head;
            for (ListNode n = head; n != null; n = n.next) {
                if (n.val != 9) lastNot9 = n; /* invariant: [lastNot9.next, tail] are all 9*/
            }
            lastNot9.val++;
            for (ListNode n = lastNot9.next; n != null; n = n.next) {
                n.val = 0;
            }
            return dmy.val == 1 ? dmy : head;
        }
    

  • 1

    For example: 8->7->9->9
    Add dummy: 0->8->7->9->9
    The lastNotNine is 7.
    7 + 1 = 8
    9 change to 0.
    We got 0->8->8->0->0
    return dummy.next

    For example: 9->9->9
    Add dummy: 0->9->9->9
    The lastNotNine is 0.
    0 + 1 = 1
    9 change to 0.
    We got 1->0->0->0
    return dummy

    public class Solution {
        public ListNode plusOne(ListNode head) {
          ListNode dummy = new ListNode(0);
          dummy.next = head;
          ListNode lastNotNine = dummy;
          ListNode node = head;
          while(node != null){
            if(node.val != 9){
              lastNotNine = node;
            }
            node = node.next;
          }  
          
          lastNotNine.val = lastNotNine.val + 1;
          lastNotNine = lastNotNine.next;
          while(lastNotNine != null){
            lastNotNine.val = 0;
            lastNotNine = lastNotNine.next;
          }
          return dummy.val == 1 ? dummy : dummy.next;
        }
    }

Log in to reply
 

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