369.md

369. Plus One Linked List

Description

Given a non-negative integer represented as non-empty singly linked list of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

Thinking Process

1. The trick of the question is that the head of the list stores the most significant digits
2. To get around that, we are interested in finding the first digit (nearest to the tail of the list) that is not a nine, mark it as firstNon9Node
3. Once firstNon9Node is found, everything after that will become 0, and the value stored in firstNon9Node will just increase by 1.

Code

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

Complexity

1. Time complexity is O(n) as the list will be scanned at most twice
2. Space complexity is O(1) as the program uses constant addtional memory