Plus one (Linked list)


  • 0
    N

    Similar to https://leetcode.com/problems/plus-one/, but digits are expressed in linked list instead of array.


    Given a non-negative number represented as a singly linked list of digits, plus one to the number.

    The digits are stored such that the most significant digit is at the head of the list.

    Example:

    Input:
    1->2->3

    Output:
    1->2->4

    Have to do it in O(n) time and O(1) space.


  • 2
    ListNode add(ListNode root) {
        if (addOne(root)  == 1)  {
            ListNode  tmp= new ListNode<>(1);
            tmp.next = root;  
            return tmp;
        }
        return root;
    }
    
    int addOne(ListNode node) {
          if  (node == null)
              return 1;
          if  (addOne(node.next) == 1) { 
              int rem = (node.val + 1)/10;
              node.val = (node.val + 1)% 10;
              return rem;
          }
          return 0;
      }

  • 0
    N

    @elmirap pretty cool to solve it recursively. However, it is not O(1) space due to O(n) auxiliary stack space.


  • 0

    @nixed yes, right, I didn't conform to the constraint


  • 0

    @elmirap I like it! This shows that recursive solution can be really elegant. Great job!


  • 0

    @1337c0d3r, @nixed thank you very much. I will post iterative solution in a while


  • 1
    ListNode addOne(ListNode root) {
          ListNode head = null;
          ListNode current = root;
          while (current != null) {
              ListNode temp = current;
              current = current.next;
              temp.next = head;
              head = temp;
          }
          int rem = 1;
          current = head;
          head = null;
          while (current != null) {
              int r = (current.val + rem)/10;
              current.val = (current.val + rem)% 10;
              rem = r;          
              ListNode temp = current;
              current = current.next;
              temp.next = head;
              head = temp;
          }
          current = head;      
          if  (rem == 1)  {
              head = new ListNode(1);
              head.next = current;
          }
          return head;
      }

Log in to reply
 

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