369.Plus-One-Linked-List

369. Plus One Linked List

题目地址

https://leetcode.com/problems/plus-one-linked-list/

题目描述

Given a non-negative integer represented as non-empty a 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.

Example :
Input: [1,2,3]
Output: [1,2,4]

代码

Approach #1 Sentinel Head

Time: O(N) && Space: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode plusOne(ListNode head) {
        // sentinel head
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode notNine = sentinel;

    // find the rightmost not-nine digit
    while (head != null) {
      if (head.val != 9)    notNine = head;
      head = head.next;
    }

    // increase thsi rightmost not-nine digit
    notNine.val++;
    notNine = notNine.next;

    while (notNine != null) {
      notNine.val = 0;
      notNine = notNie.next;
    }

    return sentinel.val != 0 ? sentinel : sentinal.next;
  }
}

Approach #2 Recursive DFS

class Solution {
  public ListNode plusOne(ListNode head) {
    if (DFS(head) == 0) {
      return head;
    } else {
      ListNode newHead = new ListNode(1);
      newHead.next = head;
      return newHead;
    }
  }

  private int DFS(ListNode head) {
    if (head == null)        return 1;

    if (DFS(head.next) == 0) { // carry
      return 0;
    }

    int val = head.val + 1;
    head.val = val % 10;
    return val / 10; // next carry
  }
}